Оценка погрешности при решении систем линейных уравнений прямым и итерационным методами решения
Автор:
Бухлакова Наталья
МБОУ «СОШ № 37», 8Б класс
Руководители:
Горлова Наталья Николаевна
Юдина Юлия Александровна
Ангарск, 2019 г.
Содержание
Введение 2 стр.
Глава I 4 стр.
1.1 История возникновения СЛАУ 4 стр.
1.2 Способы решения СЛАУ (методами Гаусса, Крамера, Якоби) 4 стр.
Глава II 16 стр.
2.1 Разработка программного обеспечения 16 стр.
2.2 Исследование зависимости величины погрешности метода Якоби от разрядности коэффициентов СЛАУ 18 стр.
Заключение 20 стр.
Список литературы 21 стр.
Введение
Многие задачи практики приводят к необходимости решать системы линейных уравнений. При конструировании инженерных сооружений, обработке результатов измерений, решении задач планирования производственного процесса и ряда других задач техники, экономики, научного эксперимента приходится решать системы линейных уравнений.
Решение систем линейных алгебраических уравнений - одна из основных задач вычислительной линейной алгебры. Большой объем расчетных математических задач приходится на решение систем линейных алгебраических уравнений. Системы линейных уравнений широко используются в задачах экономики, физики, химии и других науках. На уроках алгебры я познакомилась с понятием систем линейных уравнений. Я научилась решать системы линейных уравнений способом подстановки, способом сложения, а также графическим способом. Мне стало интересно, какими ещё способами можно решать системы линейных уравнений. Изучая необходимую литературу я выяснила, что существуют точные (прямые, аналитические) и итерационные методы решения систем линейных уравнений.
Точные методы позволяют получить решение СЛАУ за конечное число алгебраических операций. Итерационный метод даёт возможность найти приближенное решение системы с заданной степенью точности. Исходя из этого возникает необходимость выбора того или иного метода, чтобы получить эффективный результат. Возникает проблема оценки погрешности прямых и итерационных методов решения.
Объект исследования - процесс решения систем уравнений с помощью широко распространённых прямых методов Крамера, Гаусса и простого в реализации итерационного метода Якоби для оценки погрешности с использованием программы, написанной на языке программирования Pascal ABC.
Цель исследования: изучить методы Крамера, Гаусса и итерационный метод Якоби для решения систем линейных уравнений и оценить погрешность данных методов решения в зависимости от разрядности коэффициентов уравнений системы.
Задачи исследования:
1. изучить литературу по данной теме;
2. ознакомиться с методами решения систем уравнений: Крамера, Гаусса, Якоби;
3. ознакомиться с итерационным методом решения систем уравнений – методом Якоби;
4. создать компьютерные модели решения системы линейных уравнений разными способами в программе, написанной на языке программирования Pascal ABC;
5. провести оценку погрешности при решении систем численными и итерационными методами, выявить их достоинства и недостатки.
При изучении литературы по данной теме выявлено, что подавляющее большинство уравнений не могут быть решены аналитически, численные методы решения уравнений являются гораздо более мощными, нежели аналитические. На основе этого была выдвинута гипотеза.
Гипотеза: погрешность поиска корней СЛАУ зависит от разрядности коэффициентов СЛАУ при использовании итерационного метода.
За основу моей работы я взяла метод Крамера, метод Гаусса и метод Якоби. Я рассмотрела решения систем линейных уравнений с тремя неизвестными, на примерах систем, содержащих однозначные коэффициенты, двузначные, трехзначные.
Актуальность: Провести сравнительный анализ погрешности вычислений в решении систем линейных уравнений с применением точных и итерационных методов решения для выбора наиболее эффективных для меня методах решения.
Глава I
1.1 Необходимость изучения СЛАУ
Идею общего метода решения систем линейных уравнений высказал Лейбниц в 1693 году. Она была реализована швейцарским математиком Крамером в 1752 году. Он сформулировал и обосновал правило, носящее теперь его имя, которое позволяет решать системы n линейных уравнений с n неизвестными и буквенными коэффициентами. Крамер, фактически, заложил основы теории определителей, хотя и не предложил для них удобного обозначения (это сделал в 1841 году А. Кэли). В 1772 году Вандермонд опубликовал обширное исследование определителей, один из которых носит теперь его имя. Систематическое изложение этой теории принадлежит Бине и Коши. Их труды по теории определителей относятся к периоду 1812-1815 гг.
Коэффициенты системы линейных уравнений и свободные члены удобно сводить в таблицы, называемые матрицами системы. Постепенно определители систем стали относить к матрицам систем. Матричный метод решения систем линейных уравнений впервые описан в древнекитайском трактате «Девять книг о математическом искусстве» (II век до н.э.). Система линейных уравнений в этом трактате записывается в виде матрицы, столбцы которой составлены из коэффициентов при неизвестных и свободных членов, и решается методом исключения, впоследствии заново сформулированном Гауссом в 1849 году. Этот метод естественно формулируется в виде правил преобразования так называемой расширенной матрицы системы.
Исследования Вейерштрасса и Фробениуса далеко продвинули теорию матриц, обогатив ее новыми понятиями и задачами. Фробениус, в частности, ввел понятие ранга матрицы (1877 г.). Используя это понятие, Кронекер и Капелли в лекциях 1883-91 гг. (Кронекер) и 1892 г. (Капелли) излагали теорему, дающую исчерпывающий ответ на вопрос о том, при каких условиях система m линейных уравнений с n неизвестными имеет решение[6].
1.2 Способы решения СЛАУ (метод Гаусса, метод Крамера, метод Якоби)
Определение: Системой линейных уравнений называют объединение из n линейных уравнений, каждое из которых содержит k переменных
[2]
В своей работе я буду рассматривать СЛАУ вида .
Рассмотрим решение простейших систем методом Крамера и Гаусса. Каковы условия применения данных методов?
Метод Крамера применяется только в том случае, если количество переменных совпадает с количеством уравнений и составленный определитель из коэффициентов при неизвестных отличен от 0, в противном случае система решений не имеет.
Метод Гаусса применяется для уравнений, в которых коэффициенты не пропорциональны, в противном случае система будет либо иметь бесчисленное множество решений, либо решений не будет.
Метод Якоби применятся в случае, если коэффициенты системы удовлетворяют условию сходимости
, где , , . [4]
Рассмотрим задачи, которые встречаются на государственной итоговой аттестации.
Задача №1
Семья состоит из мужа, жены и их дочери студентки. Если бы зарплата мужа увеличилась вдвое, общий доход семьи вырос бы на 67%. Если бы стипендия дочери уменьшилась втрое, общий доход семьи сократился бы на 4%. Сколько процентов от общего дохода семьи составляет зарплата жены?
Решим задачу при помощи системы уравнений.
Пусть x-заработная плата мужа,
y-заработная плата жены,
z- стипендия дочери.
Весь доход семьи примем за 1.
Согласно условию составим СЛАУ и найдем ее решение по формулам Крамера и методом Гаусса, хотя проще ее было решить методом подстановки.
Для решения СЛАУ, применим формулы , где – определитель, состоит из коэффициентов при неизвестных, а - вспомогательные определители, полученные из путем замены соответствующего столбца столбцом свободных членов. [4]
.
Ответ: 27%
Решим систему методом Гаусса – составим расширенную матрицу и приведем её к треугольному виду.
По найденной матрице составим систему линейных уравнений и найдём её решение.
В ходе решения данной системы по методу Гаусса были выполнены следующие элементарные преобразования:
1) Элементы первой строки умножили на (-2) и сложили с элементами второй строки. Таким образом, были получены элементы второй строки.
2) Элементы первой строки умножили на (-1) и сложили с элементами третьей строки. Таким образом, были получены элементы третьей строки.
Задача№2
В санатории отдыхают 450 человек. Если количество женщин увеличится в два раза, количество мужчин уменьшиться в три раза, а количество детей уменьшится в два раза, то количество отдыхающих составит 500 человек. Если же количество женщин уменьшится в два раза, количество мужчин вырастет в два раза, а количество детей уменьшится в два раза, то количество отдыхающих останется прежним. Определите сколько в санатории отдыхает женщин, мужчин и детей.
Решим задачу при помощи системы уравнений.
Пусть x-количество отдыхающих женщин,
y- количество отдыхающих мужчин,
z- количество отдыхающих детей.
Согласно условию составим СЛАУ и найдем ее решение по формулам Крамера и Гаусса, хотя проще ее было решить методом подстановки.
Для решения СЛАУ, применим формулы , где – определитель, состоит из коэффициентов при неизвестных, а - вспомогательные определители, полученные из путем замены соответствующего столбца столбцом свободных членов.
.
Ответ: женщин отдыхало 200, мужчин 150, а детей 100.
Решим систему методом Гаусса – составим расширенную матрицу и приведем её к треугольному виду.
По найденной матрице составим систему линейных уравнений и найдём её решение.
В ходе решения данной системы по методу Гаусса были выполнены следующие элементарные преобразования:
1) Элементы второй строки умножили на 6, а элементы третьей строки на 2.
2) Элементы первой строки умножили на (-12) и сложили с элементами второй строки. Таким образом, были получены элементы второй строки.
3) Элементы первой строки умножим на (-1) и сложим с элементами третьей строки. Таким образом, были получены элементы третьей строки.
4) Переставим местами второй и третий столбец.
Рассмотрим серию примеров СЛАУ, которые содержат однозначные, двузначные, трехзначные и четырехзначные коэффициенты при неизвестных.
Пример 1.
Решение:
Решим систему методом Крамера, используя формулы , где – определитель, состоит из коэффициентов при неизвестных, а - вспомогательные определители, полученные из путем замены соответствующего столбца столбцом свободных членов.
СЛАУ имеет решение.
Проверка:
Решим систему методом Гаусса – составим расширенную матрицу и приведем её к треугольному виду.
По найденной матрице составим систему линейных уравнений и найдём её решение.
В ходе решения данной системы по методу Гаусса были выполнены следующие элементарные преобразования:
1) Элементы первой строки переставили с элементами второй строки.
2) Элементы первой строки умножили на (-3) и сложили с элементами второй строки. Таким образом, были получены элементы второй строки.
3) Элементы первой строки умножили на (-2) и сложили с элементами третьей строки. Таким образом, были получены элементы третьей строки.
4) Элементы второй строки переставили с элементами третьей строки.
5) Элементы второй строки умножили на (-2) и сложили с элементами третьей строки. В результате были получены элементы третьей строки.
Решим систему методом Якоби
Приведем СЛАУ к удобному виду для итерации:
Выбираем начальное приближение:
Это вектор правой части.
Первая итерация имеет следующий вид:
Аналогично вычисляем приближения к решению
Пример 2
Решение:
Решим систему методом Крамера, используя формулы , где – определитель, состоит из коэффициентов при неизвестных, а - вспомогательные определители, полученные из путем замены соответствующего столбца столбцом свободных членов.
, , .
Проверка: .
Решим систему методом Гаусса – составим расширенную матрицу и приведем её к треугольному виду.
По найденной матрице составим систему линейных уравнений и найдём её решение.
.
В ходе решения данной системы по методу Гаусса были выполнены следующие элементарные преобразования:
1) Элементы второй строки умножили на 2.
2) Элементы первой строки умножили на (-1) и сложили с элементами второй строки. Таким образом, были получены элементы второй строки.
3) Элементы второй строки поменяли с элементами первой строки.
4) Элементы первой строки умножили на (-25) и сложили с элементами второй строки. Таким образом, были получены элементы второй строки.
4) Элементы первой строки умножили на (-10) и сложили с элементами третьей строки. Таким образом, были получены элементы третьей строки.
5) Элементы второй строки умножили на 214, а элементы третьей строки умножили на (-545) и сложили. В результате были получены элементы третьей строки.
Пример 3
Решим систему методом Крамера, используя формулы , где – определитель, состоит из коэффициентов при неизвестных, а - вспомогательные определители, полученные из путем замены соответствующего столбца столбцом свободных членов. 4604060
СЛАУ имеет решение.
Проверка:
Пример 4
Решим систему методом Крамера, используя формулы , где – определитель, состоит из коэффициентов при неизвестных, а - вспомогательные определители, полученные из путем замены соответствующего столбца столбцом свободных членов.
СЛАУ имеет решение.
Проверка:
В первой главе я изучила два основных метода решения СЛАУ: метод Гаусса и метод Крамера. На мой взгляд метод Крамера пригоден для решения СЛАУ второго и третьего порядка. Позволяет решать систему в общем виде. Недостатком данного метода является то, что для СЛАУ порядка выше третьего затруднен подсчет определителя. Метод Гаусса применим к любой СЛАУ, менее трудоемкий и позволяет однозначно установить, совместна система или нет. Недостатки данного метода: не позволяет найти общие формулы, выражающие решение системы через ее коэффициенты и свободные члены, которые необходимы для написания программы на компьютере. Для меня наиболее понятным оказался метод Гаусса.
Глава II
2.1 Разработка программного обеспечения
В данном разделе представлена блок-схема, разработанной программы поиска корней СЛАУ.
Рис. 1 Блок-схема программы поиска корней СЛАУ
Рассмотренные в первой главе методы поиска корней СЛАУ реализованы в программе, разработанной в среде Pascal ABC [1].
В программе реализована процедура генерации исходных коэффициентов СЛАУ. Процедура генерации исходных коэффициентов СЛАУ основана на равновероятном законе распределения случайных чисел [3]. При этом законе распределения вероятность появления любого числа в интервале (a,b) одинакова. Для реализации равновероятного распределения в среде программирования Pascal ABC есть готовая функция random.
Рис. 2 Равновероятный закон распределения (x – случайное число, f(x) – закон распределения)
Генерация исходных данных проходит по следующему алгоритму:
1. Выбирается разрядность коэффициентов СЛАУ.
2. С помощью функции random генерируются a1, b1, c1, x, y, z в первом уравнении системы: , d1 – результат вычисления правой части уравнения.
3. Далее генерируются коэффициенты второго и третьего уравнения a2, b2, c2, a3, b3, c3 и рассчитываются коэффициенты d2, d3.
4. Для полученных коэффициентов СЛАУ проверяются условия сходимости для выбранных методов расчёта (описаны в 1 главе настоящей работы), если хоть одно условие не выполняется, то повторяется пункт 2.
2.2 Исследование зависимости величины погрешности метода Якоби от разрядности коэффициентов СЛАУ
В данном разделе представлены результаты работы разработанной программы поиска корней СЛАУ методами: Крамера, Гаусса и Якоби.
Таблица № 1. Однозначные коэффициенты СЛАУ
a b c d Метод
Крамера Метод
Гаусса Метод
Якоби
3 1 1 8 x=1 x=1 x=1
1 5 2 17 y=2 y=2 y=2
2 3 7 29 z=3 z=3 z=3
Таблица № 2. Двузначные коэффициенты СЛАУ
a b c d Метод
Крамера Метод
Гаусса Метод
Якоби
25 10 12 39 x=0,89 x=0,89 x=1,00
13 27 12 10 y=0,96 y=0,96 y=-0,99
10 12 25 48 z=2,02 z=2,02 z=2,00
Таблица № 3. Трехзначные коэффициенты СЛАУ
a b c d Метод
Крамера Метод
Гаусса Метод
Якоби
204 101 102 203 x=1 x=1 x=1.009
100 201 100 201 y=1 y=1 y=1.009
110 103 220 -7 z=-1 z=-1 z=-0.990
Таблица № 4. Четырёхзначные коэффициенты СЛАУ
a b c d Метод
Крамера Метод
Гаусса Метод
Якоби
2002 1000 1001 -1 x=-1 x=-1 x=-0.717
1003 2009 1005 2011 y=1 y=1 y=1.282
1000 1001 2003 2004 z=1 z=1 z=1.282
Согласно представленным выше таблицам для полученных исходных данных СЛАУ методы Крамера и Гаусса показали одинаковые результаты. Далее представим графики зависимости корней СЛАУ, полученных методом Крамера, Гаусса и Якоби от разрядности коэффициентов СЛАУ.
По полученным диаграммам видно, что разрядность коэффициентов СЛАУ влияет на погрешность итерационного метода Якоби решения СЛАУ. Для метода Якоби зависимость разрядности коэффициентов СЛАУ от погрешности корней СЛАУ носит сложный характер.
Заключение
В ходе проведенной работы я пришла к выводу, что погрешность поиска корней СЛАУ с единственным решением зависит от разрядности коэффициентов СЛАУ при использовании итерационного метода решения. Это говорит о подтверждении выдвинутой гипотезы. При решении методом Крамера и Гаусса погрешность можно избежать, если использовать обыкновенные дроби в отличии от метода Якоби.
Список использованной литературы:
1) Босова Л.Л. Информатика: учебник для 8 класса / Л.Л. Босова А.Ю. Босова. –2-е изд., испр.– М. : БИНОМ. Лаборатория знаний, 2014.– 160 с. :ил.
2) Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах. – М.: Высш. шк., 2006. Ч.1.
3) Гмурман В.Е. Теория вероятностей и математическая статистика: учеб. пособие. – 12-е изд., перераб. – М.: Высшее образование, Юрайт-Издат, 2009. – 479 с.
4) Общий курс высшей математики для экономистов: Учебник / Под общ. ред. В.И. Ермакова. – М. ИНФРА-М,2007. – 656с.
5) Письменный Д.Т. Конспект лекций по высшей математике. – М.: Айрис-пресс, 2002. – Ч1. – 288с.
6) Клиффорд Пиковер: Великая математика. От Пифагора до 57-мерных объектов. 250 основных вех в истории математики. Изд. : Бином, Лаборатория знаний, 2015г.
|
