Линейная алгебра, численные методы – раздел вычислительной математики, посвященный математическому описанию и исследованию процессов численного решения задач линейной алгебры.
Среди задач линейной алгебры наибольшее значение имеют две: решение системы линейных алгебраических уравнений, определение собственных значений и собственных векторов матрицы. Другие часто встречающиеся задачи: обращение матрицы, вычисление определителя и т.д.
Любой численный метод линейной алгебры можно рассматривать как некоторую последовательность выполнения арифметических операций над элементами входных данных. Если при любых входных данных численный метод позволяет найти решение задачи за конечное число арифметических операций, то такой метод называется прямым
. В противоположном случае численный метод называется итерационным
. Прямые методы - это такие, как метод Гаусса, метод окаймления, метод пополнения, метод сопряжённых градиентов и др. Итерационные методы – это метод простой итерации, метод вращений, метод переменных направлений, метод релаксации и др.
На практике в большинстве случаев найти точное решение возникшей математической задачи не удается. Это происходит главным образом не потому, что мы не умеем этого сделать, а поскольку искомое решение обычно не выражается в привычных для нас элементарных или других известных функциях. Поэтому важное значение приобрели численные методы, особенно в связи с возрастанием роли математических методов в различных областях науки и техники и с появлением высокопроизводительных ЭВМ.
Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, т.е. к тем действиям, которые выполняет ЭВМ.
В настоящее время появилось значительное число различных программных продуктов (MathCAD, MathLABи т.д.), с помощью которых, задавая только входные данные, можно решить значительное число задач.
Конечно, использование таких программных продуктов значительно сокращает время и ресурсы по решению ряда важных задач. Однако, использование этих программ без тщательного анализа метода, с помощью которого решается задача, нельзя гарантировать, что задача решена правильно. Поэтому для более полного понимания того, как осуществляется расчет различного вида уравнений и их систем, необходимо теоретически изучить методы их решения и на практике их проработать. Этим обозначается проблема
нашей работы.
Учитывая важность выше указанных проблем, тему своей работы мы определили так: «Численные методы решения систем линейных алгебраических уравнений ».
В качестве объекта
исследования выступают различные численные методы решения линейных алгебраических уравнений и систем линейных алгебраических уравнений.
Предметом
исследования, является выявление эффективности и сравнительная характеристика методов.
Задачи
исследования:
· изучить и проанализировать литературу по проблемам численных методов;
· изучить научную и учебную литературу по теме «Численные методы решения систем линейных алгебраических уравнений;
· определить основные этапы изучения темы «Численные методы решения систем линейных алгебраических уравнений»;
· продемонстрировать на примерах использование методов.
Дипломная работа состоит из введения, двух глав, заключения, списка используемой литературы (20 наименований).
Во введении обоснована актуальность темы исследования, определены объект, предмет, проблема и задачи исследования.
В первой главе изучается теория и терминология численных методов с примерами и пояснениями.
Во второй главе рассматривается применение численных методов решения линейных алгебраических уравнений в теории и на практике.
В заключении подведены итоги и сделаны основные выводы.
Глава I. Теоретические основы исследования
§1
ЧИСЛЕННЫЕ МЕТОДЫ
Разрешимость системы линейных уравнений.
Когда мы говорим о главной матрице системы линейных уравнений, то всегда имеем в виду квадратную матрицу nхn, т. е. матрицу с одинаковым количеством строк и столбцов. Это важно.
Если, например, количество строк (количество уравнений в системе) будет меньше, чем количество столбцов (фактически, количества неизвестных), то система будет неопределенной, т. е. мы не сможем однозначно определить все неизвестные (решить систему).
Но это не единственное ограничение. Из векторной алгебры известно, что система линейных уравнений имеет решение (однозначное) тогда и только тогда, когда ее главный определитель не равен нулю: Δ ≠ 0.
Рассмотрим случай, когда определитель системы равен нулю. Здесь возможны два варианта:
1. Δ = 0 и каждый из дополнительных определителей Δxi
= 0. Это имеет место только тогда, когда коэффициенты при неизвестных xi
пропорциональны, т. е. каждое уравнение системы получается из первого уравнения умножением обеих его частей на число k. При этом система имеет бесчисленное множество решений.
2. Δ = 0 и хотя бы один дополнительный определитель Δxi
≠ 0. Это имеет место только тогда, когда коэффициенты при всех неизвестных xi
, пропорциональны. При этом получается система из противоречивых уравнений, которая не имеет решений [7].
1.1
Матричный метод решения систем линейных алгебраических уравнений
Пусть дана система линейных уравнений:
Рассмотрим матрицу, составленную из коэффициентов при неизвестных:
Свободные члены и неизвестные можно записать в виде матрицы столбцов:
Тогда, используя правило умножение матриц, эту систему уравнений можно записать так:
или
A·x = b. (1)
Равенство (1) называется матричным уравнением или системой уравнений в матричном виде.
Матрица А коэффициентов при неизвестных называется главной матрицей системы.
Иногда рассматривают также расширенную матрицу системы, т. е. главную матрицу системы, дополненную столбцом свободных членов, которую записывают в следующем виде:
Любую линейную систему уравнений можно записать в матричном виде. Например, пусть дана система:
Эта система из двух уравнений с тремя неизвестными – x, y,. В высшей математике можно рассматривать системы из очень большого числа уравнений с большим количеством неизвестных и поэтому неизвестные принято обозначать только буквой х, но с индексами:
Запишем эту систему в матричном виде:
Здесь главная матрица системы:
Расширенная матрица будет иметь вид:
Microsoft
Office
Excel
.
Если же говорить о программе Excel, которая является одной из наиболее известных в обработке электронных таблиц, то без преувеличения можно утверждать, что ее возможности практически неисчерпаемы.Обработка текста, управление базами данных - программа настолько мощна, что во многих случаях превосходит специализированные программы - редакторы или программы баз данных. Такое многообразие функций может поначалу запутать, нежели заставить применять их на практике. Но по мере приобретения опыта начинаешь по достоинству ценить то, что границ возможностей Excel тяжело достичь.За всю историю табличных расчетов с применением персональных компьютеров требования пользователей к подобным программам существенно изменились. В начале основной акцент в такой программе, как, например, Visi Calc
, ставился на счетные функции. Сегодня, положение другое. Наряду с инженерными и бухгалтерскими расчетами организация и графическое изображение данных приобретают все возрастающее значение. Кроме того, многообразие функций, предлагаемое такой расчетной и графической программой, не должно осложнять работу пользователя. Программы для Windows создают для этого идеальные предпосылки.В последнее время многие как раз перешли на использование Windows в качестве своей пользовательской среды. Как следствие, многие фирмы, создающие программное обеспечение, начали предлагать большое количество программ для Windows.
MathCAD
.
Программа MathCAD по своему назначению позволяет моделировать в электронном документе научно–технические, а также экономические расчёты в форме, достаточно близкой к общепринятым ручным расчётам. Это упрощает составление программы расчёта, автоматизирует перерасчёт и построение графических иллюстраций подобно электронным таблицам Excel, документирование результатов как в текстовом редакторе Word.
Программа Mathcad известна за лёгкость, с которой математические уравнения, текст, и графика могут быть объединены в одном документе. Кроме того, вычислительные способности Mathcad распространяются от сложения столбца чисел к решению интегралов и производных, решение систем уравнений и больше.
Достоинством MathCAD является также наличие в его составе электронных книг. Одна из них – учебник по самой программе, другие – справочник по различным разделам математики, физики, радиоэлектроники и др.
К численным методам решения систем линейных уравнений относят такие как: метод Гаусса, метод Крамера, итерационные методы. В методе Гаусса, например, работают над расширенной матрицей системы. А в методе Крамера – с определителями системы, образованными по специальному правилу.
1.2 Метод Гаусса – прямой и обратный ход
Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными:
Будем считать, что a11
≠ 0 (если это не так, то достаточно переставить первую и некоторую другую строку расширенной матрицы местами). Проведем следующие элементарные преобразования:
C2
-(a21
/a11
)*C1
,
...
Cm
-(am1
/a11
)*C1
,
т.е. Ci-(ai1
/a11
)*C1
, i = 2, 3, ..., m.
Т. е. от каждой строки расширенной матрицы (кроме первой) отнимаем первую строку, умноженную на частное от деления первого элемента этой строки на диагональный элемент а11
.
В результате получим матрицу:
Т. е. первая строка осталась без изменений, а в столбце под а1
1 на всех местах оказались нули. Обратим внимание, что преобразования коснулись всех элементов строк, начиная со второй, всей расширенной матрицы системы.
Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы А – aij
, где I = j.
Повторим наши элементарные преобразования, но уже для элемента α22
.
C1
-(a12
/α22
)*C2
,
...
Cm
-(αm2
/α22
)*C2
,
т.е. Ci
-(αi2
/α22
)*C2
, i = 3, ..., m.
Т. е. от каждой строки расширенной матрицы (теперь кроме первой и второй) отнимаем вторую строку, умноженную на частное от деления первого элемента этой (текущей) строки на диагональный элемент α22
.
Такие преобразования продолжаются до тех пор, пока матрица не приведется к верхнее - треугольному виду. Т. е. под главной диагональю не окажутся все нули:
Вспомнив, что каждая строка представляет собой одно из уравнений линейной системы уравнений, легко заметить, что последнее m-ое уравнение принимает вид:
γmn
*xn
= δm
.
Отсюда легко можно найти значение первого корня – xn
= δm
/γmn
.
Подставив это значение в предыдущее m-1-е уравнение, легко получим значение xn-1
-ого корня.
Таким образом, поднимаясь до самого верха обратным ходом метода Гаусса, мы последовательно найдем все корни системы уравнений [5].
Пример 1
Рассмотрим систему уравнений:
Главный определитель данной системы:
Δ = [1*(-4)*(-2)+2*2*1+(-1)*(-1)*(-1)]-[1*(-4)*(-1)+2*(-1)*(-2)+2*(-1)*1] = [8+4-1]-[4+4-2] = 11-6 =5,
т. е. Δ ≠ 0.
Т. е. система определена и разрешима. Решим ее по методу Гаусса.
Проведем прямой ход метода Гаусса, выписав предварительно расширенную матрицу системы:
Получим нули под главной диагональю в первом столбце расширенной матрицы. Для получения нуля в элементе a21 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C2
-(a21
/a11
)*C1
= C2
-(2/1)*C1
= C2
-2*C1
:
Аналогично поступаем и с элементом а31 (т. е. под диагональю в третьей строке матрицы). Третью строку матрицы преобразуем по формуле C3
-(a31
/a11
)*C1
= C3
-(-1/1)*C1
= C3
+C1
:
Таким образом, мы получили нули под главной диагональю в первом столбце расширенной матрицы. Осталось получить нуль под главной диагональю во втором столбце матрицы, т. е. на месте элемента а32. Для этого третью строку матрицы преобразуем по формуле C3
-(a32
/a22
)*C2
= C3
-(1/-2)*C2
= C3
+1/2C2
:
Таким образом, проведя прямой ход метода Гаусса
, мы получили расширенную матрицу системы, приведенную к верхне-треугольному виду:
Эта матрица эквивалентна системе:
Обратным ходом метода Гаусса
найдем корни системы. Из последнего уравнения найдем корень х3
:
-5/2x3
= 3/2,
x3
= (3/2):(-5/2) = 3/2*(-2/5) = -3/5.
Корень x3
= -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2x2
-3x3
= 1):
-2x2
-3(-3/5) = 1,
-2x2
+9/5 = 1,
-2x2
= 1-9/5,
-2x2
= -4/5,
x2
= (-4/5):(-2) = (-4/5)*(-1/2) = 2/5.
Корень x2
= 2/5 найден. Подставим его и корень х3
в верхнее (первое) уравнение системы (x1
-x2
+x3
= 0):
x1
-2/5+(-3/5) = 0,
x1
-5/5 = 0,
x1
= 5/5 = 1.
Проверка:
т. е.
т. е.
и т. д [9].
Вывод:
Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:
1. Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхнее - треугольной матрицей. Эти действия называют прямым ходом.
2. Из полученной треугольной системы переменные находят с помощью последовательных подстановок (обратный ход).
3. При этом все преобразования проводятся над так называемой расширенной матрицей системы, которую и приводят к верхнее - треугольному виду в прямом ходе метода.
1.3
Итерация для линейных систем
Способ итераций дает возможность получить последовательность приближенных значений, сходящихся к точному решению системы, подобно тому, как это делается для одного уравнения.
Для определенности ограничимся системой из четырех уравнений с четырьмя неизвестными (система четвертого порядка), которую запишем в виде:
Разрешим первое уравнение системы относительно х1
:
х1
= (-a12
/a11
)х2
-a13
/a11
х3
-a14
/a11
х4
-a15
/a11
.
Затем разрешим второе уравнение относительно х2
и т. д. Тогда систему можно переписать в виде:
гдеα = -aik
/aii
, i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5.
Система является частным случаем записи вида:
При этом линейная функция L1
фактически не зависит от х1
.
Зададим какие-либо начальные значения неизвестных (нулевые приближения):
х1
(0)
, х2
(0)
, х3
(0)
, х4
(0)
.
Подставляя эти значения в правые части системы (*), получим первые приближения:
Полученные первые приближения могут быть так же использованы для получения вторых, третьих и т. д. приближений. Т. е. можно записать:
Условия сходимости итерационного процесса.
Установим условия, выполнение которых обеспечит сходимость получающихся приближений к истинному (точному) решению системы х1
, х2
, х3
, х4
.
Не вдаваясь в подробности, скажем, что для того чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными.
Это условие можно сформулировать и более точно [20]:
Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы
:
1.4 Итерация Якоби
Рассмотрим систему линейных уравнений:
Уравнения можно записать в виде:
Это позволяет предложить следующий итерационный процесс:
или (другой вид записи)
Покажем, что если начать с точки P0
= (х1
(0)
, х2
(0)
, х3
(0)
, х4
(0)
) = (1, 2, 2), то итерация (3) сходится к решению (2, 4, 3). Подставим х1
= 1, х2
= 2, х2
= 2 в правую часть каждого уравнения из (3), чтобы получить новые значения:
Новая точка P1
= (х1
(1)
, х2
(1)
, х3(1)
, х4
(1)
) = (1.75, 3.375, 3), ближе, чем P0
.
Итерация, использующая (3), генерирует последовательность точек {Pk
}, которая сходится к решению (2, 4, 3):
| k | х1(k) | х2(k) | х3(k) |
| 0 | 1.0 | 2.0 | 2.0 |
| 1 | 1.75 | 3.375 | 3.0 |
| 2 | 1.84375 | 3.875 | 3.025 |
| 3 | 1.9625 | 3.925 | 2.9625 |
| 4 | 1.990625 | 3.9765625 | 3.0 |
| 5 | 1.99414063 | 3.9953125 | 3.0009375 |
| … | … | … | … |
| 15 | 1.99999993 | 3.99999985 | 3.0009375 |
| … | … | … | … |
| 19 | 2.0 | 4.0 | 3.0 |
Этот процесс называется итерацией Якоби
и может использоваться для решения определенных типов линейных систем [19].
1.5 Итерация Гаусса-Зейделя
Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости.
Отметим, что итеративный процесс Якоби производит три последовательности – {х1
(k)
}, {х2
(k)
}, {х3
(k)
}, {х4
(k)
}. Кажется разумным, что х1
(k+1)
может быть использовано вместо х2
(k
). Аналогично х1
(k+1)
и х2
(k+1)
можно использовать в вычислении х3
(k+1)
. Например, для уравнений из системы (1) это даст следующий вид итерационного процесса Гаусса-Зейделя, использующий (3*):
Такой итерационный процесс даст результаты:
| k | х1
(k) |
х2
(k) |
х3
(k) |
| 0 | 1.0 | 2.0 | 2.0 |
| 1 | 1.75 | 3.75 | 2.95 |
| 2 | 1.95 | 3.96875 | 2.98625 |
| 3 | 1.995625 | 3.99609375 | 2.99903125 |
| … | … | … | … |
| 8 | 1.99999983 | 3.99999988 | 2.99999996 |
| 9 | 1.99999998 | 3.99999999 | 3.0 |
| 10 | 2.0 | 4.0 | 3.0 |
Т. е. к точному решению мы пришли уже на 10-ом шаге итерации, а не на 19, как в итерации Якоби [19].
Вывод:
1. Способ итераций дает возможность получить последовательность приближенных значений, сходящихся к точному решению системы. Для этого система приводится к виду (для случая системы из четырех уравнений):
Эти формулы как раз и задают собственно итерационный процесс.
2. При этом чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными.
Это условие можно сформулировать и более точно:
Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы:
3. Следует так же сказать, что итерационный процесс может пров
Глава 2. Применение численных методов для решения систем линейных алгебраических уравнений в теории и на практике
§1 ЧИСЛЕННЫЕ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
Существуют два типа методов — прямые и итерационные. Мы рассматриваем прежде всего метод исключения Гаусса для систем общего вида и варианты — метод прогонки и методы матричной прогонки для систем специального вида (с трех-диагональной или блочно-трех диагональной матрицами). Это — прямые методы.
Их эффективность зависит от порядка системы n структуры матрицы.
При изучении итерационных
методов мы трактуем систему уравнений как операторное уравнение первого рода Au
=
f
и излагаем общую теорию итерационных методов для операторных уравнений при минимальных предположениях относительно оператора А.
Общая теория позволяет доказать сходимость итераций для метода Зейделя и метода верхней релаксации при минимальных ограничениях на оператор А.
Рассмотрены два класса методов: 1) для случая, когда известны границы γi
> О и γ2
>= γ1
спектра оператора А
в некотором энергетическом пространстве HD
;
2) для случая, когда границы γ1
и γ2
неизвестны. Весьма эффективным является попеременно-треугольный метод.
Основная задача линейной алгебры — решение системы уравнений
Au
=
f
,
(1)
где u=(u(1)
, ..., u(
N
)
) — искомый вектор, f={f(1)
, f(2)
,... ..., f(
n
)
)—известный вектор размерности N
,
A
=(
aij
) (
i
,
j
= 1, 2, ..., N
)
— квадратная матрица размера NXNс элементами aij
.
Будем предполагать, что матрица А
невырождена, так что уравнение Аи = 0
имеет только тривиальное решение, и система (1) имеет единственноерешение
В курсе линейной алгебры решение системы (1) обычно выражают по формулам Крамера в виде отношений определителей. Для численного решения системы (1) эти формулы непригодны, так как они требуют вычисления N +1 определителей, что требует большого числа действий (порядка N! арифметических операций). Даже при выборе наилучшего метода вычисление одного определителя требует примерно такого же времени, что и решение системы линейных уравнений современными численными методами. Кроме того, следует иметь в виду, что вычисления по формулам Крамера часто ведут к большим ошибкам округлений.
Особенность большинства численных методов для (1) состоит в отказе от нахождения обратной матрицы. Основное требование к методу решения — минимум числа арифметических действий, достаточных для отыскания приближенного решения с заданной точностью е>0 (экономичность численного метода).
Выбор того или иного численного метода зависит от многих обстоятельств — от имеющихся программ, от вида матрицы А,
от типа расчета и др. Поясним слова «тип расчета». Возможны разные постановки задачи:
1) найти решение одной конкретной задачи (1);
2) найти решение нескольких вариантов задачи (1) с одной и той же матрицей А
и разными правыми частями. Может оказаться, что неоптимальный для одной задачи метод является весьма эффективным для многовариантного расчета.
При многовариантном расчете можно уменьшить среднее число операций для одного варианта, если хранить некоторые величины, а не вычислять их заново для каждого варианта. Это, конечно, зависит от машины, от объема ее оперативной памяти.
При теоретических оценках качества алгоритмов их сравнение проводится по числу q
(
e
)
арифметических действий, достаточных для нахождения решения задачи с заданной точностью е > 0 [15].
Прямые методы
Метод Гаусса.
Имеется несколько вычислительных вариантов метода Гаусса, основанного на идее последовательного исключения. Процесс решения системы линейных алгебраических уравнений Ax
=
f
(1) по методу Гаусса состоит из двух этапов.
Первый этап (прямой ход).
Система (1) приводится к треугольному виду
х + В*х
= φ, (2)
где x
=(
x
1
, ..
., xN
-) - неизвестный, φ= (φ1,…,
φN
) —известный векторы, В*
— верхняя треугольная матрица.
Второй этап (обратный ход).
Неизвестные х
N
,
xN
-1
, ..., x
1
определяются по формулам (2) .
Метод квадратного корня.
Этот метод пригоден для систем
Au
=
f
(3)
с эрмитовой (в действительном случае — симметричной) матрицей А.
Матрица А
разлагается в произведение
А
-= S
*
DS
,
(4)
где S — верхняя треугольная, D
—
диагональная матрица. Решение уравнения Аu=fсводится к последовательному решению двух систем
S
*
Dy
=
f
,
Su
=
y
.
(5)
Метод квадратного корня требует порядка N2
/3 арифметических действий, т. е. при больших N
он вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти. Это обстоятельство объясняется тем, что метод использует информацию о симметрии матрицы.
Итерационные методы
1. Метод итераций для решения системы линейных
алгебраических уравнений
.
Перейдем к общему описанию метода итераций
для системы линейных алгебраических уравнений
Au=f (6)
Для ее решения выбирается некоторое начальное приближение у0
H
и последовательно находятся приближенные решения (итерации) уравнения (1). Значение итерации
yh
+1
выражается через известные предыдущие итерации yk
,
yk
-1
,…
Если при вычислении yh
+1
используется только одна предыдущая итерация yh
,
то итерационный метод называют одношаговым
(или двухслойным)
методом; если же yk
+1
выражается через две итерации yk
и yk
-1
, то метод называется двухшаговым
(или трехслойным).
Мы будем рассматривать в основном одношаговые методы. Будем считать, что А:
H
->
H
— линейный оператор в конечномерном пространстве H
со скалярным произведением (•, •).
Важную роль играет запись итерационных методов в единой (канонической) форме. Любой двухслойный итерационный метод можно записать в следующей канонической форме:
(7), где А: Н
-> Н —
оператор исходного уравнения (1), В: Н -> Н
— линейный оператор, имеющий обратный В-1
,
k
—
номер итерации, τ1
τ2
, ..., τk
+1
,
...— итерационные параметры, τk
+1
> 0. Оператор В
может, вообще говоря, зависеть от номера k
-
для Для простоты изложения мы предполагаем всюду, что В
не зависит от k
.
Если В
= Е
— единичный оператор, то метод(8) называют явным:
yh
+1
находится по явной формуле
В общем случае, при В≠ Е,
метод (7) называют неявным
итерационным методом: для определения yh
+1
надо решить уравнение:
(9)
Естественно требовать, чтобы объем вычислений для решения .системы Byk
+1
= Fk
был меньше, чем объем вычислений для прямого решения системы Au=f
Точность итерационного метода (7) характеризуется величиной погрешности zh
= ук
— и,
т. е. разностью между решением уравнения (7) и точным решением и
исходной системы линейных алгебраических уравнений. Подстановка yk
=
zk
+
u
в (2) приводит к однородному уравнению для погрешности:
§2 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
2.1 Общие сведения
К численным методам линейной алгебры относятся численные методы решения систем линейных алгебраических уравнений. Методы решения СЛАУ разбиваются на две группы. К первой группе принадлежат так называемые точные или прямые методы - алгоритм, позволяющий получить решение системы за конечное число арифметических действий. Вторую группу составляют приближенные методы, в частности итерационные методы решения СЛАУ.
2.2.1 Описание метода
Рассмотрим СЛАУ вида
Ax = B, где А - матрица. (1)
A = {aij
}i, j = 1…n
B = {bi
}x = {xi
}
Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру
xk
= Cxk
-1
+ D
xk
→ x*, где х* - решение заданной системы.
В конечном варианте система будет имееть вид:
x1
=c11
x1
+c12
x2
+c13
x3
+…c1n
xn
+d1
x2
=c21
x1
+c22
x2
+c23
x3
+…c2n
xn
+d1
x3
=c31
x1
+c32
x2
+c33
x3
+…c1n
xn
+d3
…………………………………………. .
xn
=cn1
x1
+cn2
x2
+cn3
x3
+…cnn
xn
+dn
Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.
, или .
Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.
Для преобразования системы можно выполнить следующие операции:
x1=
a11
-1
(c1
-a12
x2
- a13
x3
-… - a1n
xn
)
x2=
a22
-1
(c2
-a21
x2
- a23
x3
-… - a2n
xn
)
………………………. .
xn=
ann
-1
(cn
-an1
x2
- an3
x3
-… - an-1n
xn-1
)
В результате получим систему:
x1=
0+ c12
x2
+ c13
x3
-…+ c1
n
-1
xn
-1
+ c1
n
xn
+d1
x2=
c21
x2
+0 +c23
x3
+…+ c2n-1
xn-1
+ c2n
xn
+d2
………………………………………………………. .
xn=
cn1
x1
+ cn2
x2
+cn3
x3
+…+ cnn-1
xn-1
+ 0+dn
В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:
сij
=-aij
/aii
, di
=ci
/aii
(i,j=1,2,3…n, i<>j)
Итерационный процесс продолжается до тех пор, пока значения х1
(
k
),
х2
(
k
),
х3
(
k
)
не станут близкими с заданной погрешностью к значениям х1
(
k
-1),
х2
(
k
-1),
х3
(
k
-1).
2.2.2 Решение СЛАУ методом простых итераций
Решить СЛАУ методом простых итераций с точностью .
Для удобства преобразуем систему к виду:
Условие сходимости:
,
Принимаем приближение на 0-ом шаге:
,
,
На 1-м шаге выполняем следующее:
Подставляем принятые приближения в первоначальную систему уравнений
Смотрим не выполняется ли условие остановки итерационного процесса:
:
На 2-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса
:
На 3-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса
:
На 4-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса
:
На 5-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса:
:
На 6-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса:
:
Необходимая точность достигнута на 6-й итерации. Таким образом, итерационный процесс можно прекратить [14].
2.3 Метод Зейделя
2.3.1 Описание метода
В этом методе результаты, полученные на k-том шаге, используются на этом же шаге. На (k+1) - й итерации компоненты приближения вычисляются по формулам:
………………………………………….
Этот метод применим к система уравнений в виде Ax=B при условии, что диагональный элемент матрицы коэффициентов A по модулю должен быть больше, чем сумма модулей остальных элементов соответствующей строки (столбца).
Если данное условие выполнено, необходимо проследить, чтобы система была приведена к виду, удовлетворяющему решению методом простой итерации и выполнялось необходимое условие сходимости метода итераций:
, либо
2.3.2 Решение СЛАУ методом Зейделя
Решить СЛАУ методом Зейделя с точностью .
Эту систему можно записать в виде:
В этой системе сразу видно, что выполняется условие, где диагональные элементы матрицы коэффициентов по модулю больше, чем сумма модулей остальных элементов соответствующей строки.
Для удобства преобразуем систему к виду:
Условие сходимости:
,
Принимаем приближение на 0-ом шаге:
На 1-м шаге выполняем следующее:
Подставляем принятые приближения в первоначальную систему уравнений
Смотрим не выполняется ли условие остановки итерационного процесса
:
На 2-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса
:
На 3-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса:
:
На 4-м шаге выполняем следующее:
Смотрим не выполняется ли условие остановки итерационного процесса
:
Необходимая точность достигнута на 4-й итерации. Таким образом, итерационный процесс можно прекратить [9].
2.4 Сравнительный анализ
Можно заметить, что в методе Зейделя быстрее мы достигаемой нужной точности, в нашем случае в точность была достигнута на 4-й итерации, когда в методе простых итераций она была достигнута на 6-й итерации. Но в то же время в методе Зейделя ставится больше условий. Поэтому вначале нужно произвести иногда довольно трудоемкие преобразования. В таблице 4.1 приведены результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации:
Таблица 4.1 - Результаты решения СЛАУ
| № шага | Метод постой итерации | Метод Зейделя |
| 0 | x1
x2
x3
x4
|
x1
x2
x3
x4
|
| 1 | x1
x2
x3
x4
|
x1
x2
x3
x4
|
| 2 | x1
x2
x3
x4
|
x1
x2
x3
x4
|
| 3 | x1
x2
x3
x4
|
x1
x2
x3
x4
|
| 4 | x1
x2
x3
x4
|
x1
x2
x3
x4
|
| 5 | x1
x2
x3
x4
|
|
| 6 | x1
x2
x3
x4
|
Заключение
Огромное количество численных методов ставит актуальной задачей не столько создание новых, сколько исследование и классификацию старых, выявление лучших. Анализ влияния ошибок показал, что между лучшими методами нет принципиальной разницы с точки зрения устойчивости к ошибкам округления. Создание мощных компьютеров существенно ослабило значение различия между методами (в таких характеристиках, как объём требуемой памяти, количество арифметических операций). В этих условия наиболее предпочтительными становятся те методы, которые не очень отличаются от лучших по скорости и удобству реализации на компьютерах, позволяют решать широкий класс задач как хорошо, так и плохо обусловленных и давать при этом оценку точности вычислительного решения.
В MathCAD и Excel численные методы представляют собой те же самые общепринятые ручные расчёты, но выполняемые не человеком, а компьютером, что понижает возможность ошибки до нуля. Программа на VisualBasic намного упрощает задачу. С помощью единожды созданной программы можно решать системы линейных уравнений, вводя минимум значений. Также эта программа может быть использована не только вами, но и простыми пользователями.
В ходе выполнения дипломной работы был проведен сравнительный анализ численных методов, таких как итерация, интерполяция, метод Эйлера.
В результаты все поставленные задачи были выполнены, цели достигнуты. Мы приобрели навыки в применении различных численных методов на практике. А также были исследованы различные методы.
Теперь перед нами стоит задача в применении приобретенных знаний в своей будущей профессиональной деятельности.
Список литературы:
1. Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров. М.: Высш. шк., 2004. 544 с.
2. Калиткин Н.Н. Численные методы. М.: Наука, 2003. 512 с.
3. Райс Дж. Матричные вычисления и математическое обеспечение. М.: Мир, 2004. 264 с.
4. Демидович Б.П., Марон И.А. Основы вычислительной математики. М.: Наука, 2000. 664 с.
5. Воробьева Г.Н., Данилова А.Н. Практикум по численным методам. М.: Высш. шк., 2009. 184 с.
6. Тихонов А.Н., Костомаров Д.П. Вводные лекции по прикладной математике. М.: Наука, 2004. 190 с.
7. Беклемишев Д.В. Дополнительные главы линейной алгебры. М.: Наука, 2003. 335 с.
8. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 2006. 320 с.
9. Годунов С.К. Решение систем линейных уравнений. Новосибирск: Наука,2000.
10. М. Додж, К. Кината, К. Стинсон "Эффективная работа в Microsoft Excel 97", издательство "Питер"; Санкт-Петербург, 2008г.11. Е.К. Овчаренко, О.П. Ильина, Е.В. Балыбердин "Финансово - экономические расчеты в Excel", Москва, 2009 г.12. Йорг Шиб, Excel 7,0: Сотни полезных рецептов, Дюссельдорф-Киев-Москва- Санкт-Петербург, 2007 г.
13. Симонович С.В. и др. Информатика Базовый курс: Учеб, для технических вузов. СПБ: Изд. «Питер», 2004.–640с
14. Калиткин Н.Н. и др. Численные методы. М.: Наука, 2002
15. Турчак Л.И. Основы численных методов. М.: Наука, 2007
16. Дьяконов В.П. Система MathCAD. М.: Радио и связь, 2003
17. Р.Ф. Хемминг "Численные методы (для научных работников и инженеров)". - Москва, 2002.
18. А.А. Амосов, А.Ю. Дубинский, Н.В. Копченова "Вычислительные методы для инженеров". - Москва, "Высшая школа", 2004.
19. Ф.В. Формалев, Д.Л. Ревизников "Численные методы". - М.: ФИЗМАТЛИТ, 2004.
20. Е.А. Волков. Численные методы: Учеб. Пособие для вузов - М.: Наука. Гл. ред. физ-мат. лит., 2007. - 248 с.