Реферат: Численные методы решения систем линейных алгебраических уравнений

Введение

Линейная алгебра, численные методы – раздел вычислительной математики, посвященный математическому описанию и исследованию процессов численного решения задач линейной алгебры.

Среди задач линейной алгебры наибольшее значение имеют две: решение системы линейных алгебраических уравнений, определение собственных значений и собственных векторов матрицы. Другие часто встречающиеся задачи: обращение матрицы, вычисление определителя и т.д.

Любой численный метод линейной алгебры можно рассматривать как некоторую последовательность выполнения арифметических операций над элементами входных данных. Если при любых входных данных численный метод позволяет найти решение задачи за конечное число арифметических операций, то такой метод называется прямым . В противоположном случае численный метод называется итерационным . Прямые методы - это такие, как метод Гаусса, метод окаймления, метод пополнения, метод сопряжённых градиентов и др. Итерационные методы – это метод простой итерации, метод вращений, метод переменных направлений, метод релаксации и др.

На практике в большинстве случаев найти точное решение возникшей математической задачи не удается. Это происходит главным образом не потому, что мы не умеем этого сделать, а поскольку искомое решение обычно не выражается в привычных для нас элементарных или других известных функциях. Поэтому важное значение приобрели численные методы, особенно в связи с возрастанием роли математических методов в различных областях науки и техники и с появлением высокопроизводительных ЭВМ.

Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, т.е. к тем действиям, которые выполняет ЭВМ.

В настоящее время появилось значительное число различных программных продуктов (MathCAD, MathLABи т.д.), с помощью которых, задавая только входные данные, можно решить значительное число задач.

Конечно, использование таких программных продуктов значительно сокращает время и ресурсы по решению ряда важных задач. Однако, использование этих программ без тщательного анализа метода, с помощью которого решается задача, нельзя гарантировать, что задача решена правильно. Поэтому для более полного понимания того, как осуществляется расчет различного вида уравнений и их систем, необходимо теоретически изучить методы их решения и на практике их проработать. Этим обозначается проблема нашей работы.

Учитывая важность выше указанных проблем, тему своей работы мы определили так: «Численные методы решения систем линейных алгебраических уравнений ».

В качестве объекта исследования выступают различные численные методы решения линейных алгебраических уравнений и систем линейных алгебраических уравнений.

Предметом исследования, является выявление эффективности и сравнительная характеристика методов.

Задачи исследования:

· изучить и проанализировать литературу по проблемам численных методов;

· изучить научную и учебную литературу по теме «Численные методы решения систем линейных алгебраических уравнений;

· определить основные этапы изучения темы «Численные методы решения систем линейных алгебраических уравнений»;

· продемонстрировать на примерах использование методов.

Дипломная работа состоит из введения, двух глав, заключения, списка используемой литературы (20 наименований).

Во введении обоснована актуальность темы исследования, определены объект, предмет, проблема и задачи исследования.

В первой главе изучается теория и терминология численных методов с примерами и пояснениями.

Во второй главе рассматривается применение численных методов решения линейных алгебраических уравнений в теории и на практике.

В заключении подведены итоги и сделаны основные выводы.

Глава I. Теоретические основы исследования

§1 ЧИСЛЕННЫЕ МЕТОДЫ

Разрешимость системы линейных уравнений.

Когда мы говорим о главной матрице системы линейных уравнений, то всегда имеем в виду квадратную матрицу nхn, т. е. матрицу с одинаковым количеством строк и столбцов. Это важно.

Если, например, количество строк (количество уравнений в системе) будет меньше, чем количество столбцов (фактически, количества неизвестных), то система будет неопределенной, т. е. мы не сможем однозначно определить все неизвестные (решить систему).

Но это не единственное ограничение. Из векторной алгебры известно, что система линейных уравнений имеет решение (однозначное) тогда и только тогда, когда ее главный определитель не равен нулю: Δ ≠ 0.

Рассмотрим случай, когда определитель системы равен нулю. Здесь возможны два варианта:

1. Δ = 0 и каждый из дополнительных определителей Δx_i = 0. Это имеет место только тогда, когда коэффициенты при неизвестных x_i пропорциональны, т. е. каждое уравнение системы получается из первого уравнения умножением обеих его частей на число k. При этом система имеет бесчисленное множество решений.

2. Δ = 0 и хотя бы один дополнительный определитель Δx_i ≠ 0. Это имеет место только тогда, когда коэффициенты при всех неизвестных x_i , пропорциональны. При этом получается система из противоречивых уравнений, которая не имеет решений [7].

1.1 Матричный метод решения систем линейных алгебраических уравнений

Пусть дана система линейных уравнений:

Рассмотрим матрицу, составленную из коэффициентов при неизвестных:

Свободные члены и неизвестные можно записать в виде матрицы столбцов:

Тогда, используя правило умножение матриц, эту систему уравнений можно записать так:

или

A·x = b. (1)

Равенство (1) называется матричным уравнением или системой уравнений в матричном виде.

Матрица А коэффициентов при неизвестных называется главной матрицей системы.

Иногда рассматривают также расширенную матрицу системы, т. е. главную матрицу системы, дополненную столбцом свободных членов, которую записывают в следующем виде:

Любую линейную систему уравнений можно записать в матричном виде. Например, пусть дана система:

Эта система из двух уравнений с тремя неизвестными – x, y,. В высшей математике можно рассматривать системы из очень большого числа уравнений с большим количеством неизвестных и поэтому неизвестные принято обозначать только буквой х, но с индексами:

Запишем эту систему в матричном виде:

Здесь главная матрица системы:

Расширенная матрица будет иметь вид:

MathCAD .

Программа MathCAD по своему назначению позволяет моделировать в электронном документе научно–технические, а также экономические расчёты в форме, достаточно близкой к общепринятым ручным расчётам. Это упрощает составление программы расчёта, автоматизирует перерасчёт и построение графических иллюстраций подобно электронным таблицам Excel, документирование результатов как в текстовом редакторе Word.

Программа Mathcad известна за лёгкость, с которой математические уравнения, текст, и графика могут быть объединены в одном документе. Кроме того, вычислительные способности Mathcad распространяются от сложения столбца чисел к решению интегралов и производных, решение систем уравнений и больше.

Достоинством MathCAD является также наличие в его составе электронных книг. Одна из них – учебник по самой программе, другие – справочник по различным разделам математики, физики, радиоэлектроники и др.

К численным методам решения систем линейных уравнений относят такие как: метод Гаусса, метод Крамера, итерационные методы. В методе Гаусса, например, работают над расширенной матрицей системы. А в методе Крамера – с определителями системы, образованными по специальному правилу.

1.2 Метод Гаусса – прямой и обратный ход

Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными:

Будем считать, что a₁₁ ≠ 0 (если это не так, то достаточно переставить первую и некоторую другую строку расширенной матрицы местами). Проведем следующие элементарные преобразования:

C₂ -(a₂₁ /a₁₁ )*C₁ ,

...

C_m -(a_m1 /a₁₁ )*C₁ ,

т.е. Ci-(a_i1 /a₁₁ )*C₁ , i = 2, 3, ..., m.

Т. е. от каждой строки расширенной матрицы (кроме первой) отнимаем первую строку, умноженную на частное от деления первого элемента этой строки на диагональный элемент а₁₁ .

В результате получим матрицу:

Т. е. первая строка осталась без изменений, а в столбце под а₁ 1 на всех местах оказались нули. Обратим внимание, что преобразования коснулись всех элементов строк, начиная со второй, всей расширенной матрицы системы.

Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы А – a_ij , где I = j.

Повторим наши элементарные преобразования, но уже для элемента α₂₂ .

C₁ -(a₁₂ /α₂₂ )*C₂ ,

...

C_m -(α_m2 /α₂₂ )*C₂ ,

т.е. C_i -(α_i2 /α₂₂ )*C₂ , i = 3, ..., m.

Т. е. от каждой строки расширенной матрицы (теперь кроме первой и второй) отнимаем вторую строку, умноженную на частное от деления первого элемента этой (текущей) строки на диагональный элемент α₂₂ .

Такие преобразования продолжаются до тех пор, пока матрица не приведется к верхнее - треугольному виду. Т. е. под главной диагональю не окажутся все нули:

Вспомнив, что каждая строка представляет собой одно из уравнений линейной системы уравнений, легко заметить, что последнее m-ое уравнение принимает вид:

γ_mn *x_n = δ_m .

Отсюда легко можно найти значение первого корня – x_n = δ_m /γ_mn .

Подставив это значение в предыдущее m-1-е уравнение, легко получим значение x_n-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 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C₂ -(a₂₁ /a₁₁ )*C₁ = C₂ -(2/1)*C₁ = C₂ -2*C₁ :

Аналогично поступаем и с элементом а31 (т. е. под диагональю в третьей строке матрицы). Третью строку матрицы преобразуем по формуле C₃ -(a₃₁ /a₁₁ )*C₁ = C₃ -(-1/1)*C₁ = C₃ +C₁ :

Таким образом, мы получили нули под главной диагональю в первом столбце расширенной матрицы. Осталось получить нуль под главной диагональю во втором столбце матрицы, т. е. на месте элемента а32. Для этого третью строку матрицы преобразуем по формуле C₃ -(a₃₂ /a₂₂ )*C₂ = C₃ -(1/-2)*C₂ = C₃ +1/2C₂ :

Таким образом, проведя прямой ход метода Гаусса , мы получили расширенную матрицу системы, приведенную к верхне-треугольному виду:

Эта матрица эквивалентна системе:

Обратным ходом метода Гаусса найдем корни системы. Из последнего уравнения найдем корень х₃ :

-5/2x₃ = 3/2,

x₃ = (3/2):(-5/2) = 3/2*(-2/5) = -3/5.

Корень x₃ = -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2x₂ -3x₃ = 1):

-2x₂ -3(-3/5) = 1,

-2x₂ +9/5 = 1,

-2x₂ = 1-9/5,

-2x₂ = -4/5,

x₂ = (-4/5):(-2) = (-4/5)*(-1/2) = 2/5.

Корень x₂ = 2/5 найден. Подставим его и корень х₃ в верхнее (первое) уравнение системы (x₁ -x₂ +x₃ = 0):

x₁ -2/5+(-3/5) = 0,

x₁ -5/5 = 0,

x₁ = 5/5 = 1.

Проверка:

т. е.

т. е.

и т. д [9].

Вывод: Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:

1. Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхнее - треугольной матрицей. Эти действия называют прямым ходом.

2. Из полученной треугольной системы переменные находят с помощью последовательных подстановок (обратный ход).

3. При этом все преобразования проводятся над так называемой расширенной матрицей системы, которую и приводят к верхнее - треугольному виду в прямом ходе метода.

1.3 Итерация для линейных систем

Способ итераций дает возможность получить последовательность приближенных значений, сходящихся к точному решению системы, подобно тому, как это делается для одного уравнения.

Для определенности ограничимся системой из четырех уравнений с четырьмя неизвестными (система четвертого порядка), которую запишем в виде:

Разрешим первое уравнение системы относительно х₁ :

х₁ = (-a₁₂ /a₁₁ )х₂ -a₁₃ /a₁₁ х₃ -a₁₄ /a₁₁ х₄ -a₁₅ /a₁₁ .

Затем разрешим второе уравнение относительно х₂ и т. д. Тогда систему можно переписать в виде:

гдеα = -a_ik /a_ii , i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5.

Система является частным случаем записи вида:

При этом линейная функция L₁ фактически не зависит от х₁ .

Зададим какие-либо начальные значения неизвестных (нулевые приближения):

х₁ ⁽⁰⁾ , х₂ ⁽⁰⁾ , х₃ ⁽⁰⁾ , х₄ ⁽⁰⁾ .

Подставляя эти значения в правые части системы (*), получим первые приближения:

Полученные первые приближения могут быть так же использованы для получения вторых, третьих и т. д. приближений. Т. е. можно записать:

Условия сходимости итерационного процесса.

Установим условия, выполнение которых обеспечит сходимость получающихся приближений к истинному (точному) решению системы х₁ , х₂ , х₃ , х₄ .

Не вдаваясь в подробности, скажем, что для того чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными.

Это условие можно сформулировать и более точно [20]:

Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы :

1.4 Итерация Якоби

Рассмотрим систему линейных уравнений:

Уравнения можно записать в виде:

Это позволяет предложить следующий итерационный процесс:

или (другой вид записи)

Покажем, что если начать с точки P₀ = (х₁ ⁽⁰⁾ , х₂ ⁽⁰⁾ , х₃ ⁽⁰⁾ , х₄ ⁽⁰⁾ ) = (1, 2, 2), то итерация (3) сходится к решению (2, 4, 3). Подставим х₁ = 1, х₂ = 2, х₂ = 2 в правую часть каждого уравнения из (3), чтобы получить новые значения:

Новая точка P₁ = (х₁ ⁽¹⁾ , х₂ ⁽¹⁾ , х3⁽¹⁾ , х₄ ⁽¹⁾ ) = (1.75, 3.375, 3), ближе, чем P₀ .

Итерация, использующая (3), генерирует последовательность точек {P_k }, которая сходится к решению (2, 4, 3):

Этот процесс называется итерацией Якоби и может использоваться для решения определенных типов линейных систем [19].

1.5 Итерация Гаусса-Зейделя

Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости.

Отметим, что итеративный процесс Якоби производит три последовательности – {х₁ ^(k) }, {х₂ ^(k) }, {х₃ ^(k) }, {х₄ ^(k) }. Кажется разумным, что х₁ ^(k+1) может быть использовано вместо х₂ ^(k ). Аналогично х₁ ^(k+1) и х₂ ^(k+1) можно использовать в вычислении х₃ ^(k+1) . Например, для уравнений из системы (1) это даст следующий вид итерационного процесса Гаусса-Зейделя, использующий (3*):

Такой итерационный процесс даст результаты:

Т. е. к точному решению мы пришли уже на 10-ом шаге итерации, а не на 19, как в итерации Якоби [19].

Вывод:

1. Способ итераций дает возможность получить последовательность приближенных значений, сходящихся к точному решению системы. Для этого система приводится к виду (для случая системы из четырех уравнений):

Эти формулы как раз и задают собственно итерационный процесс.

2. При этом чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными.

Это условие можно сформулировать и более точно:

Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы:

3. Следует так же сказать, что итерационный процесс может проводиться как в виде итерации Якоби, так и в виде итерации Гаусса-Зейделя. В последнем случае сходимость итерационного процесса может существенно улучшиться.

Глава 2. Применение численных методов для решения систем линейных алгебраических уравнений в теории и на практике

§1 ЧИСЛЕННЫЕ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Существуют два типа ме­тодов — прямые и итерационные. Мы рассматриваем прежде всего метод исключения Гаусса для систем об­щего вида и варианты — метод прогонки и методы мат­ричной прогонки для систем специального вида (с трех-диагональной или блочно-трех диагональной матрицами). Это — прямые методы. Их эффективность зависит от по­рядка системы n структуры матрицы.

При изучении итерационных методов мы трактуем си­стему уравнений как операторное уравнение первого ро­да Au = f и излагаем общую теорию итерационных ме­тодов для операторных уравнений при минимальных предположениях относительно оператора А. Общая тео­рия позволяет доказать сходимость итераций для метода Зейделя и метода верхней релаксации при минимальных ограничениях на оператор А. Рассмотрены два класса методов: 1) для случая, когда известны границы γ_i > О и γ₂ >= γ₁ спектра оператора А в некотором энергетиче­ском пространстве H_D ; 2) для случая, когда границы γ₁ и γ₂ неизвестны. Весьма эффективным является попере­менно-треугольный метод.

Основная задача линейной ал­гебры — решение системы уравнений

Au = f , (1)

где u=(u⁽¹⁾ , ..., u^{( N )} ) — искомый вектор, f={f⁽¹⁾ , f⁽²⁾ ,... ..., f^{( n )} )—известный вектор размерности N , A =( a_ij ) ( i , j = 1, 2, ..., N ) — квадратная матрица размера NXNс элементами a_ij .

Будем предполагать, что матрица А невырождена, так что уравнение Аи = 0 имеет только триви­альное решение, и система (1) имеет единственноерешение

В курсе линейной алгебры решение системы (1) обыч­но выражают по формулам Крамера в виде отношений определителей. Для численного решения системы (1) эти формулы непригодны, так как они требуют вычисления N +1 определителей, что требует большого числа дей­ствий (порядка N! арифметических операций). Даже при выборе наилучшего метода вычисление одного определи­теля требует примерно такого же времени, что и реше­ние системы линейных уравнений современными числен­ными методами. Кроме того, следует иметь в виду, что вычисления по формулам Крамера часто ведут к боль­шим ошибкам округлений.

Особенность большинства численных методов для (1) состоит в отказе от нахождения обратной матрицы. Ос­новное требование к методу решения — минимум числа арифметических действий, достаточных для отыскания приближенного решения с заданной точностью е>0 (экономичность численного метода).

Выбор того или иного численного метода зависит от многих обстоятельств — от имеющихся программ, от вида матрицы А, от типа расчета и др. Поясним слова «тип расчета». Возможны разные постановки задачи:

1) найти решение одной конкретной задачи (1);

2) найти решение нескольких вариантов задачи (1) с одной и той же матрицей А и разными правыми частями. Может оказаться, что неоптимальный для одной задачи метод является весьма эффективным для мно­говариантного расчета.

При многовариантном расчете можно уменьшить сред­нее число операций для одного варианта, если хранить некоторые величины, а не вычислять их заново для каж­дого варианта. Это, конечно, зависит от машины, от объ­ема ее оперативной памяти.

При теоретических оценках каче­ства алгоритмов их сравнение проводится по числу q ( e ) арифметических действий, достаточных для нахождения решения задачи с заданной точностью е > 0 [15].

Прямые методы

Метод Гаусса. Имеется несколько вычислительных вариантов метода Гаусса, основанного на идее последо­вательного исключения. Процесс решения системы ли­нейных алгебраических уравнений Ax = f (1) по методу Гаусса состоит из двух этапов.

Первый этап (прямой ход). Система (1) приво­дится к треугольному виду

х + В*х = φ, (2)

где x =( x ₁ , .. ., x_N -) - неизвестный, φ= (φ_1,…, φ_N ) —известный векторы, В* — верхняя треугольная матрица.

Второй этап (обратный ход). Неизвестные х _N , x_{N -1} , ..., x ₁ определяются по формулам (2) .

Метод квадратного корня. Этот метод пригоден для систем

Au = f (3)

с эрмитовой (в действительном случае — симметричной) матрицей А. Матрица А разлагается в произведение

А -= S * DS , (4)

где S — верхняя треугольная, D — диагональная матрица. Решение уравнения Аu=fсводится к последователь­ному решению двух систем

S * Dy = f , Su = y . (5)

Метод квадратного корня требует порядка N² /3 арифметических действий, т. е. при больших N он вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти. Это обстоятельство объясняется тем, что метод использует информацию о симметрии матрицы.

Итерационные методы

1. Метод итераций для решения системы линейных алгебраических уравнений .

Перейдем к общему описанию метода итераций для системы линейных алгебраических уравнений

Au=f (6)

Для ее решения выбирается некоторое начальное приближение у₀ H и последовательно находятся приближенные решения (итерации) уравнения (1). Значение итерации y_{h +1} выражается через известные предыдущие итерации y_k , y_{k -1} ,… Если при вычислении y_{h +1} используется толь­ко одна предыдущая итерация y_h , то итерационный метод называют одношаговым (или двухслойным) методом; если же y_{k +1} выражается через две итерации y_k и y_{k -1} , то метод называется двухшаговым (или трехслойным). Мы будем рассматривать в основном одношаговые методы. Будем считать, что А: H -> H — линейный оператор в конеч­номерном пространстве H со скалярным произведе­нием (•, •).

Важную роль играет запись итерационных методов в единой (канонической) форме. Любой двухслойный ите­рационный метод можно записать в следующей канони­ческой форме:

(7), где А: Н -> Н — оператор исходного уравнения (1), В: Н -> Н — линейный оператор, имеющий обратный В^-1 , k — номер итерации, τ₁ τ₂ , ..., τ_{k +1} , ...— итерационные параметры, τ_{k +1} > 0. Оператор В может, вообще говоря, зависеть от номера k - для Для простоты изложения мы пред­полагаем всюду, что В не зависит от k .

Если В = Е — единичный оператор, то метод(8) называют явным: y_{h +1} находится по явной формуле

В общем случае, при В≠ Е, метод (7) называют не­явным итерационным методом: для определения y_{h +1} надо решить уравнение:

(9)

Естественно требовать, чтобы объем вычислений для ре­шения .системы By_{k +1} = F_k был меньше, чем объем вы­числений для прямого решения системы Au=f

Точность итерационного метода (7) характеризуется величиной погрешности z_h = у_к — и, т. е. разностью между решением уравнения (7) и точным решением и исход­ной системы линейных алгебраических уравнений. Под­становка y_k = z_k + u в (2) приводит к однородному урав­нению для погрешности:

§2 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

2.1 Общие сведения

К численным методам линейной алгебры относятся численные методы решения систем линейных алгебраических уравнений. Методы решения СЛАУ разбиваются на две группы. К первой группе принадлежат так называемые точные или прямые методы - алгоритм, позволяющий получить решение системы за конечное число арифметических действий. Вторую группу составляют приближенные методы, в частности итерационные методы решения СЛАУ.

2.2.1 Описание метода

Рассмотрим СЛАУ вида

Ax = B, где А - матрица. (1)

A = {a_ij }i, j = 1…n

B = {b_i }x = {x_i }

Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру

x_k = Cx_{k -1} + D

x_k → x*, где х* - решение заданной системы.

В конечном варианте система будет имееть вид:

x₁ =c₁₁ x₁ +c₁₂ x₂ +c₁₃ x₃ +…c_1n x_n +d₁

x₂ =c₂₁ x₁ +c₂₂ x₂ +c₂₃ x₃ +…c_2n x_n +d₁

x₃ =c₃₁ x₁ +c₃₂ x₂ +c₃₃ x₃ +…c_1n x_n +d₃

_{…………………………………………. .}

x_n =c_n1 x₁ +c_n2 x₂ +c_n3 x₃ +…c_nn x_n +d_n

Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.

, или .

Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.

Для преобразования системы можно выполнить следующие операции:

x₁₌ a₁₁ ^-1 (c₁ -a₁₂ x₂ - a₁₃ x₃ -… - a_1n x_n )

x₂₌ a₂₂ ^-1 (c₂ -a₂₁ x₂ - a₂₃ x₃ -… - a_2n x_n )

………………………. .

x_n= a_nn ^-1 (c_n -a_n1 x₂ - a_n3 x₃ -… - a_n-1n x_n-1 )

В результате получим систему:

x₁₌ 0+ c₁₂ x₂ + c₁₃ x₃ -…+ c_{1 n -1} x_{n -1} + c_{1 n} x_n +d₁

x₂₌ c₂₁ x₂ +0 +c₂₃ x₃ +…+ c_2n-1 x_n-1 + c_2n x_n +d₂

_{………………………………………………………. .}

x_n= c_n1 x₁ + c_n2 x₂ +c_n3 x₃ +…+ c_nn-1 x_n-1 + 0+d_n

В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:

с_ij =-a_ij /a_ii , d_i =c_i /a_ii (i,j=1,2,3…n, i<>j)

Итерационный процесс продолжается до тех пор, пока значения х₁ ^{( k ),} х₂ ^{( k ),} х₃ ^{( k )} не станут близкими с заданной погрешностью к значениям х₁ ^{( k -1),} х₂ ^{( k -1),} х₃ ^{( 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 - Результаты решения СЛАУ

Заключение

Огромное количество численных методов ставит актуальной задачей не столько создание новых, сколько исследование и классификацию старых, выявление лучших. Анализ влияния ошибок показал, что между лучшими методами нет принципиальной разницы с точки зрения устойчивости к ошибкам округления. Создание мощных компьютеров существенно ослабило значение различия между методами (в таких характеристиках, как объём требуемой памяти, количество арифметических операций). В этих условия наиболее предпочтительными становятся те методы, которые не очень отличаются от лучших по скорости и удобству реализации на компьютерах, позволяют решать широкий класс задач как хорошо, так и плохо обусловленных и давать при этом оценку точности вычислительного решения.

В 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.

13. Симонович С.В. и др. Информатика Базовый курс: Учеб, для технических вузов. СПБ: Изд. «Питер», 2004.–640с

14. Калиткин Н.Н. и др. Численные методы. М.: Наука, 2002

15. Турчак Л.И. Основы численных методов. М.: Наука, 2007

16. Дьяконов В.П. Система MathCAD. М.: Радио и связь, 2003

17. Р.Ф. Хемминг "Численные методы (для научных работников и инженеров)". - Москва, 2002.

18. А.А. Амосов, А.Ю. Дубинский, Н.В. Копченова "Вычислительные методы для инженеров". - Москва, "Высшая школа", 2004.

19. Ф.В. Формалев, Д.Л. Ревизников "Численные методы". - М.: ФИЗМАТЛИТ, 2004.

20. Е.А. Волков. Численные методы: Учеб. Пособие для вузов - М.: Наука. Гл. ред. физ-мат. лит., 2007. - 248 с.