Итерационные методы решения систем линейных уравнений реферат
Обновлено: 05.07.2024
В данной статье мы расскажем общие сведения об итерационных методах решения СЛАУ, познакомим с методом Зейделя и Якоби, а также приведем примеры решения систем линейных уравнений при помощи данных методов.
Общие сведения об итерационных методах или методе простой итерации
Метод итерации — это численный и приближенный метод решения СЛАУ.
Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня x 0 .
Рассмотрим систему A x = b .
Чтобы применить итерационный метод, необходимо привести систему к эквивалентному виду x = B x + d . Затем выбираем начальное приближение к решению СЛАУ x ( 0 ) = ( x 1 0 , x 2 0 , . . . x m 0 ) и находим последовательность приближений к корню.
Для сходимости итерационного процесса является достаточным заданное условие В 1 . Окончание итерации зависит от того, какой итерационный метод применили.
Метод Якоби
Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 1-го уравнения матрицы выражаем неизвестное x 1 , из 2-го выражаем неизвестное x 2 и т.д.
Результатом служит матрица В , в которой на главной диагонали находятся нулевые элементы, а все остальные вычисляются по формуле:
b i j = - a i j / a i i , i , j = 1 , 2 . . . , n
Элементы (компоненты) вектора d вычисляются по следующей формуле:
d i = b i / a i i , i = 1 , 2 , . . . , n
Расчетная формула метода простой итерации:
x ( n + 1 ) = B x ( x ) + d
Матричная запись (координатная):
x i ( n + 1 ) = b i 1 x n 1 + b i 2 x ( n ) 2 + . . . + b
Критерий окончания в методе Якоби:
x ( n + 1 ) - x ( n ) ε 1 , где ε 1 = 1 - B B ε
В случае если B 1 / 2 , то можно применить более простой критерий окончания итераций:
x ( n + 1 ) - x ( n ) ε
Решить СЛАУ методом Якоби:
10 x 1 + x 2 - x 3 = 11 x 1 + 10 x 2 - x 3 = 10 - x 1 + x 2 + 10 x 3 = 10
Необходимо решить систему с показателем точности ε = 10 - 3 .
Приводим СЛАУ к удобному виду для итерации:
x 1 = - 0 , 1 x 2 + 0 , 1 x 3 + 1 , 1 x 2 = - 0 , 1 x 1 + 0 , 1 x 3 + 1 x 3 = 0 , 1 x 1 - 0 , 1 x 2 + 1
Выбираем начальное приближение, например: x ( 0 ) = 1 , 1 1 1 — вектор правой части.
В таком случае, первая итерация имеет следующий внешний вид:
x 1 ( 1 ) = - 0 , 1 × 1 + 0 , 1 × 1 + 1 , 1 = 1 , 1 x 2 ( 1 ) = - 0 , 1 × 1 , 1 + 0 , 1 + 1 = 0 , 99 x 3 ( 1 ) = 0 , 1 × 1 , 1 - 0 , 1 × 1 + 1 = 1 , 01
Аналогичным способом вычисляются приближения к решению:
x ( 2 ) = 1 , 102 0 , 991 1 , 011 , x ( 3 ) = 1 , 102 0 , 9909 1 , 0111 , x ( 4 ) = 1 , 10202 0 , 99091 1 , 01111
Находим норму матрицы В , для этого используем норму B ∞ .
Поскольку сумма модулей элементов в каждой строке равна 0,2, то B ∞ = 0 , 2 1 / 2 , поэтому можно вычислить критерий окончания итерации:
x ( n + 1 ) - x ( n ) ε
Далее вычисляем нормы разности векторов:
x ( 3 ) - x ( 2 ) ∞ = 0 , 002 , x ( 4 ) - x ( 3 ) ∞ = 0 , 00002 .
Поскольку x ( 4 ) - x ( 3 ) ∞ ε , то можно считать, что мы достигли заданной точности на 4-ой итерации.
x 1 = 1 , 102 ; x 2 = 0 , 991 ; x 3 = 1 ,01 1 .
Метод Зейделя
Метод Зейделя — метод является модификацией метода Якоби.
Суть: при вычислении очередного ( n + 1 ) - г о приближения к неизвестному x i при i > 1 используют уже найденные ( n + 1 ) - е приближения к неизвестным x 1 , x 2 , . . . , x i — 1 , а не n - о е приближение, как в методе Якоби.
x i ( n + 1 ) = b i 1 x 1 ( n + 1 ) + b i 2 x 2 ( n + 1 ) + . . . + b i , i - 1 x i - 2 ( n + 1 ) + b i , i + 1 x i + 1 ( n ) +
+ . . . + b i m x m ( n ) + d i
За условия сходимости и критерий окончания итераций можно принять такие же значения, как и в методе Якоби.
Решить СЛАУ методом Зейделя. Пусть матрица системы уравнений А — симметричная и положительно определенная. Следовательно, если выбрать начальное приближение, метод Зейделя сойдется. Дополнительных условий на малость нормы некоторой матрицы не накладывается.
Решим 3 системы уравнений:
2 x 1 + x 2 = 3 x 1 - 2 x 2 = 1 , x 1 + 2 x 2 = 3 2 x 1 - x 2 = 1 , 2 x 1 - 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1
Приведем системы к удобному для итерации виду:
x 1 ( n + 1 ) = - 0 , 5 x 2 ( n ) + 1 , 5 x 2 ( n + 1 ) = 0 , 5 x 1 ( n + 1 ) + 0 , 5 , x 1 ( n + 1 ) = - 2 x 2 ( n ) + 3 x 2 ( n + 1 ) = 2 x 1 ( n + 1 ) - 1 , 2 x 1 - 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1 .
Отличительная особенность, условие сходимости выполнено только для первой системы:
Вычисляем 3 первых приближения к каждому решению:
1-ая система: x ( 0 ) = 1 , 5 - 0 , 5 , x ( 1 ) = 1 , 75 0 , 375 , x ( 2 ) = 1 , 3125 0 , 1563 , x ( 3 ) = 1 , 4219 0 , 2109
Решение: x 1 = 1 , 4 , x 2 = 0 , 2 . Итерационный процесс сходится.
2-ая система: x ( 0 ) = 3 - 1 , x ( 1 ) = 5 9 , x ( 2 ) = - 15 - 31 , x ( 3 ) = 65 129
Итерационный процесс разошелся.
Решение: x 1 = 1 , x 2 = 2
3-я система: x ( 0 ) = 1 , 5 2 , x ( 1 ) = 2 - 6 , x ( 2 ) = 0 2 , x ( 3 ) = 0 2
Итерационный процесс зациклился.
Решение: x 1 = 1 , x 1 = 2
Метод простой итерации
Если А — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:
x = x - τ ( A x - b ) , τ - итерационный параметр.
Расчетная формула имеет следующий внешний вид:
x ( n + 1 ) = x ( n ) - τ ( A x n - b ) .
Здесь B = E - τ A и параметр τ > 0 выбирают таким образом, чтобы по возможности сделать максимальной величину B 2 .
Пусть λ m i n и λ m a x - максимальные и минимальные собственные значения матрицы А .
τ = 2 / ( λ m i n + λ m a x ) - оптимальный выбор параметра. В этом случае B 2 принимает минимальное значение, которое равняется ( λ m i n + λ m a x ) / ( λ m i n - λ m a x ) .
Данная курсовая работа включает в себя три итерационных метода решения систем линейных алгебраических уравнений (СЛАУ):
1. Метод Якоби (метод итераций).
2. Метод Холецкого.
3. Метод верхней релаксации.
Также данная курсовая работа включает в себя: описание метода, применение метода к конкретной задаче (анализ), код программы решения вышеперечисленных методов на языке программирования BorlandC++ Builder 6.
Описание метода
Метод решения задачи называют итерационным , если в результате получают бесконечную последовательность приближений к решению. Основное достоинство итерационных методов состоит в том, что точность искомого решения задается. Число итераций, которое необходимо выполнить для получения заданной точности , является основной оценкой качества метода. По этому числу проводится сравнение различных методов.
Главным недостатком этих методов является то, что вопрос сходимости итерационного процесса требует отдельного исследования. Примером обычных итерационных методов служат: метод итераций (метод Якоби), метод Зейделя, метод верхних релаксаций.
Начнем с метода итераций или как его ещё называют метода Якоби.
Существует сиcтема A·x = f (1), где матрица A = [aij ] (i, j = 1, 2, …m ) имеет обратную матрицу; x = (x1 , x2 , x3 ,… xm ) – вектор неизвестных, f – вектор свободных членов. Систему (1) нужно преобразовать к следующему виду: (2) i=1, 2,…, m, где , , при этом aii0.
Значение суммы считается равным 0, если верхний предел суммирования меньше нижнего. Тогда при i=1 уравнение имеет вид: (3). В методе Якоби исходят из записи системы в виде (2), итерации при этом определяют следующим образом: , (n=0, 1, …, n0, i=1, 2, …, m) (4).
Если последовательность приближений x1 (0) , x2 (0) ,…, xm (0) , x1 (1) , x2 (1) ,…, xm (1) ,…, x1 (k) , x2 (k) ,… , xm (k) имеет предел , , то этот предел является решением системы (2).
Достаточным условием сходимости решения системы (1) является то, что матрица A является матрицей с преобладающими диагональными элементами, то есть , i=1, 2, …, m.
Теперь рассмотрим второй итерационный метод – метод Зейделя , который является модификацией метода Якоби. Основная его идея заключается в том, что при вычислении (k +1) – го приближения неизвестной xi учитываются уже вычисленные ранее (k +1) – е приближения (x1 x2 ,…, xi-1 ).
Пусть дана приведенная линейная система: (i = 1, 2, …n ) (5). Выбираются произвольно начальные приближения корней x1 (0) , x2 (0) ,…, x n (0) , чтобы они в какой-то мере соответствовали неизвестным x1 , x2 , x3 ,…, xn .
Предполагается, что k -е приближение корней известно, тогда в соответствии с идеей метода строится (k +1) – е приближение по следующим формулам:
Если выполняется достаточное условие сходимости для системы (5) – по строкам, то в методе Зейделя выгодно расположить уравнения (6) так, чтобы первое уравнение системы имело наименьшую сумму модулей коэффициентов: .
Теперь рассмотри 3 метод – метод верхних релаксаций .
Метод верхней релаксации – это есть метод Зейделя с заданным числовым параметром w.
Одним из наиболее распространенных одношаговых методов является метод верхних релаксаций, который имеет следующий вид (7), где w заданный числовой параметр (0 при вычислениях они могут быть записаны в один и тот же массив. При реализации метода верхних релаксаций используется следующая форма записи алгоритма вычислений .
Действительно, при последовательном нахождении элемента (i+10 итерации) на каждом шаге будут использоваться найденные ранее значения, которые при k
TForm1 *Form1;
int n=0, prov=0, k=0;
float A[x] [x], B[x] [x];
float C[x], Y[x];
bool fl1=false;
__fastcall TForm1:TForm1 (TComponent* Owner)
: TForm(Owner)
void __fastcall TForm1: ButtonOkClick (TObject *Sender)
Memo1->Lines->Clear();
TryStrToInt (Edit1->Text, n);
StringGrid1->Enabled=true;
StringGrid1->RowCount=n;
StringGrid1->ColCount=n+1;
ButtonClear->Enabled=true;
ButtonOk->Enabled=false;
StringGrid1->Color=clWindow;
ButtonYakobi->Enabled=true;
ButtonZeydel->Enabled=true;
ButtonRelax->Enabled=true;
X=new float[n];
for (int i=0; i Enabled=false;
StringGrid1->RowCount=0;
StringGrid1->ColCount=0;
ButtonClear->Enabled=false;
ButtonOk->Enabled=true;
StringGrid1->Color=clBtnFace;
ButtonYakobi->Enabled=false;
void __fastcall TForm1: ButtonYakobiClick (TObject *Sender)
//TryStrToFloat (Edit2->Text, e);
Memo1->Lines->Clear();
e=StrToFloat (Edit2->Text);
for (int i=0; i Cells[j] [i], A[i] [j]);
for (int i=0; i Lines->Add(p);
Memo1->Lines->Add (« Количество итераций = «+FloatToStr(k));
void __fastcall TForm1: ButtonExitClick (TObject *Sender)
void __fastcall TForm1: RadioButton2Click (TObject *Sender)
ButtonYakobi->Visible=false;
ButtonZeydel->Visible=true;
ButtonRelax->Visible=false;
void __fastcall TForm1: RadioButton1Click (TObject *Sender)
ButtonYakobi->Visible=true;
ButtonZeydel->Visible=false;
ButtonRelax->Visible=false;
void __fastcall TForm1: ButtonZeydelClick (TObject *Sender)
Memo1->Lines->Clear();
e=StrToFloat (Edit2->Text);
for (int i=0; i Cells[j] [i], A[i] [j]);
for (int i=0; i Lines->Add(p);
Memo1->Lines->Add (« Количество итераций = «+FloatToStr(k));
void __fastcall TForm1: RadioButton3Click (TObject *Sender)
ButtonYakobi->Visible=false;
ButtonZeydel->Visible=false;
ButtonRelax->Visible=true;
void __fastcall TForm1: ButtonRelaxClick (TObject *Sender)
//TryStrToFloat (Edit2->Text, e);
v_sh=StrToFloat (Edit3->Text);
e=StrToFloat (Edit2->Text);
Memo1->Lines->Clear();
for (int i=0; i Cells[j] [i], A[i] [j]);
for (int i=0; i Lines->Add(p);
Memo1->Lines->Add (« Количество итераций = «+FloatToStr(k));
* Данная работа не является научным трудом, не является выпускной квалификационной работой и представляет собой результат обработки, структурирования и форматирования собранной информации, предназначенной для использования в качестве источника материала при самостоятельной подготовки учебных работ.
Государственное общеобразовательное учреждение высшего профессионального образования
ЛЕНИНГРАДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМЕНИ А.С. ПУШКИНА
Кафедра информатики и вычислительной математики
Решение систем линейных алгебраических уравнений методом простых итераций и методом Зейделя
студент IV курса
Метод итераций 5
Описание метода 5
Сходимость метода 8
Метод Зейделе 10
Описание метода 10
Сходимость метода. 13
Другая форма метода Зейделя 15
Практическая часть 18
Листинг №1(метод простой итерации) 18
Листинг №2(метод Зейделя) 20
Список используемой литературы 24
Введение
Способы решения линейных систем уравнений разделяют в на 2 группы.
Первые, точные методы представляющие собой конечные алгорифмы для вычисления корней системы (таковыми например, являются правило Крамера, метод Гаусса, метод главных элементов, метод квадратных корней и др.).
Вторые, итерационные методы позволяющие получить корни системы с заданной точностью путем сходящихся бесконечных процессов (к числу таковых относят, метод итераций, метод Зейделя, метод релаксации).
Вследствие неизбежных округлений результаты даже точных методов являются округленными, причем оценка погрешностей корней в общем случае затруднительна.
При использовании итерационных процессов, сверх того, добавляется погрешность метода.
Заметим, что эффективное применение итерационных методов существенно зависит от удачного выбора приближения и быстроты итерационного процесса.
Сейчас разберем несколько определений которые будем использовать в этой работе.
Система линейных уравнений с n неизвестными (или, линейная система) в линейной алгебре — это система уравнений вида
Предполагая, что диагональные коэффициенты и т. д. Тогда получим эквивалентную систему
Систему (2) можем записать в матричной форме
Далее строим матрицы столбцы
при малы по абсолютной величине. Иными словами, для успешного применения процесса итерации модули диагональных коэффициентов системы (1) должны быть велики по сравнению с модулями недиагональных коэффициентов этой системы (свободные члены при этом роли не играют).
ГОСТ
Для решения систем линейных уравнений используется два основных метода решений, прямые методы, также называемые точными и итерационные методы, при использовании которых ответ в любом случае будет приближённым.
Особенность прямых методов состоит в том, что вычисления в них всегда проводятся точно, например, с использованием целых чисел, но при этом эти методы трудно применимы для вычисления решений для больших систем. К прямому методу относится, например, метод Крамера.
Ниже подробно рассмотрены итерационные методы решения СЛАУ.
Сущность итерационных методов решения систем линейных уравнений
Как уже отмечалось выше, итерационные методы в принципе являются приближёнными. Их сущность состоит в том, что сначала записывается некоторая последовательность столбцов матрицы, после чего производится поочередное вычисление каждого столбца. Каждый новый столбец вычисляется на основе вычисленных предыдущих, при этом с каждым вычислением получается всё более точное приближение искомого решения. Когда достигнута необходимая точность, процесс вычисления прерывают и в качестве решения используют последний вычисленный столбец.
Процесс вычисления одного столбца называется итерацией.
Различают несколько основных способов итерационного решения СЛАУ:
Метод Якоби (метод простых итераций СЛАУ)
Рассмотрим систему уравнений, с коэффициентами, которые можно записать в виде матрицы:
$A=\left(\begin a_ & a_ & … & a_ \\ a_ & a_ & … & a_ \\ … & … & … & … \\ a_ & a_ & … & a_ \\ \end\right)$
Саму же систему уравнений можно записать в виде равенства $A \cdot X = F$, где $X$ — вектор-столбец собственных значений системы, а $F$ — вектор-столбец свободных членов.
Метод состоит в том, чтобы в каждом уравнении системы выразить соответственно $x_1, x_2,…, x_n$ и затем получить новую матрицу $B$, у которой элементы главной диагонали принимают нулевые значения.
В общем виде формула для вычисления корней уравнений записывается так: $\overrightarrow= B\overrightarrow + \overrightarrow$
Добиться такого вида от системы можно следующими способами:
Готовые работы на аналогичную тему
$B= E – D^A=D^(D-A), \overrightarrow = D^\overrightarrow;$
$B=-D^(L+U)=-D^(A-D), \overrightarrow = D^\overrightarrow;$
Здесь $D$ — матрица, у которой нулевые все элементы, кроме элементов на главной диагонали, а на главной диагонали находятся соответствующие элементы матрицы $A$. Матрицы $U$ и $L$ означают верхнетреугольную матрицу и нижнетреугольную соответственно; их значимые элементы соответствуют частям матрицы $A$. Буквой $Е$ же обозначается единичная матрица соответствующей размерности.
Процедура нахождения корней тогда запишется так:
$\overrightarrow^= B\overrightarrow^ + \overrightarrow$
Для конкретного элемента она будет выглядеть так:
$x_^=\frac(b_i - \sum\limits_ a_ij\cdot x_j^(k)\left(1\right)$, где $i=1,2,…, n$
буквой $(k)$ во всех формулах выше обозначается номер итерации, сама же формула $(1)$ называется рекуррентной.
Окончание вычисления происходит в том случае, если разница между вычислениями в двух соседних итераций составляет не более чем $ε_1$:
В упрощённой форме условие окончания итераций выглядит как $||x^-x^||$
Порядок решения СЛАУ методом Якоби такой:
- Приведение системы уравнений к виду, в котором на каждой строчке выражено какое-либо неизвестное значение системы.
- Произвольный выбор нулевого решения, в качестве него можно взять вектор-столбец свободных членов.
- Производим подстановку произвольного нулевого решения в систему уравнений, полученную под пунктом 1.
- Осуществление дополнительных итераций, для каждой из которых используется решение, полученное на предыдущем этапе.
Метод Гаусса-Зейделя
Сущность этого метода состоит в том, что в нём переносятся в правые части все члены уравнений, индекс при которых больше индекса, выражаемого $x$. В краткой форме это можно записать так:
$(L + D) \cdot \overrightarrow = -U\overrightarrow + \overrightarrow$
Сами итерации в методе Гаусса-Зейделя производятся по формуле:
$(L +D)\overrightarrow^=-U\overrightarrow^ + \overrightarrow$
Метод Гаусса-Зейделя похож на метод Якоби, но здесь полученные значения переменных используются не исключительно для следующей итерации, а сразу для следующего вычисления значения $x$.
Метод простых итераций: пример решения
Дана система уравнений:
$\begin 10x_1 – x_2 + 2x_3 = 6 \\ -x_1 + 11x_2 – x_3 + 3x_4 = 25 \\ 2x_1- x_2 + 10x_3 -x_4 = -11 \\ 3x_2 – x_3 + 8x_4 = 15 \end$
Решите данную систему с помощью метода простых итераций.
Выберем в качестве нулевого приближения корни $(0; 0; 0; 0)$ и подставим их в преобразованную систему:
$\begin x_1 = (6 + 0 – (2 \cdot 0))/10 = 0,6 \\ x_2 = (25 + 0 – 0 – (3 \cdot 0))/11 = 25/11 = 2,2727 // x_3 = (-11 – (2 \cdot 0) + 0 + 0) /10 = -1,1 \\ x_4 = (15 – (3 \cdot 0) + 0) / 8 = 1,875\\ \end$
Проведём 5 итераций, используя на каждой результат, полученный с предыдущей и для них получим следующую таблицу:
Рисунок 1. Таблица итераций для решения СЛАУ. Автор24 — интернет-биржа студенческих работ
Продолжать вычисление можно до достижения заданной требуемой точности. Точный ответ системы — $(1; 2; -1; 1)$.
Читайте также: