- •Часть 3
- •Введение
- •Требования к оформлению лабораторных работ
- •1. Приближенное решение нелинейных уравнений
- •2. Решение систем линейных алгебраических уравнений
- •Метод Гаусса
- •Метод Гаусса-Зейделя.
- •2: Writeln ('Количество итераций выше допустимого');
- •3. Аппроксимация функций с помощью метода наименьших квадратов
- •Нахождение параметров линейной функции
- •Нахождение параметров квадратичной функции
- •4. Решение обыкновенных дифференциальных уравнений
- •5. Многомерная оптимизация. Линейное программирование
- •Графический метод решения задачи линейного программирования.
- •Список литературы
- •Содержание
Метод Гаусса-Зейделя.
Данный метод является одним из самых распространенных итерационных методов решения СЛАУ, поскольку он отличается простотой и легкостью программирования. Рассмотрим его суть. Допустим, диагональные коэффициенты исходной матрицы {aij}отличны от нуля (в противном случае можно переставить местами уравнения исходной системы). Представим исходную систему (2.1) в следующем виде:
(2.5) |
Если теперь задать для неизвестных их начальные приближенные значения , то система (2.5) позволяет вычислить более точные значения неизвестных на первом шаге (на первой итерации):
(2.6) |
Используя найденные значения неизвестных, можно еще более уточнить их на второй итерации:
(2.7) |
и так далее.
В данном методе для нахождения значения i-го неизвестного на каждой итерации используются значения предыдущих неизвестных, уже найденные на данной итерации. Общую формулу определения i-го неизвестного на k-й итерации для системы n уравнений можно записать так:
i = 1, 2, … , n; k = 1, 2, …
|
(2.8) |
Итерационный процесс продолжается до тех пор, пока все значения xi(k), не станут достаточно близкими к xi(k-1). Близость этих значений можно охарактеризовать максимальной абсолютной величиной их разности . Тогда при заданной точности вычислений > 0 критерий окончания итерационного процесса можно записать в виде
. |
(2.9) |
При выполнении этого условия итерационный процесс называется сходящимся. В этом случае максимальные разности между значениями соответствующих неизвестных в двух последовательных итерациях убывают, а сами значения стремятся к решению системы.
Доказано, что для сходимости итерационного процесса достаточно, чтобы модули диагональных коэффициентов для каждого уравнения были не меньше суммы модулей всех остальных коэффициентов:
, |
(2.10) |
При этом хотя бы для одного уравнения неравенство (2.10) должно выполняться строго.
В качестве примера рассмотрим решение методом Гаусса-Зейделя системы (2.2). Заметим, что достаточное условие сходимости итерационного процесса (2.10) для этой системы соблюдается. Запишем исходную систему в виде
В качестве начальных приближений возьмем нули, т.е. примем x2(0) = x3(0)= 0.
Найдем значения неизвестных на первой итерации:
Далее произведем вторую итерацию:
Производя аналогично третью и последующие итерации, найдем:
x1(3) = 0,984; x2(3) = 1,981; x3(3) = 2,953;
x1(4) = 1,015; x2(4) = 1,992; x3(4) = 2,988;
x1(5) = 0,999; x2(4) = 1,993; x3(3) = 2,997.
Нетрудно заметить, что разности между значениями соответствующих неизвестных в процессе итераций убывают, следовательно, процесс решения сходящийся, что и следовало ожидать. Если принять точность вычислений = 0,02, то итерации следует закончить. При увеличении заданной точности вычисления корней, число итераций возрастает, например, при = 0,00001 следует выполнить 11 итераций, а результат будет x1(11) = 1,000000; x2(11) = 1,999998; x3(11) = 2,999999.
Программа для решения СЛАУ методом Гаусса-Зейделя приведена ниже. Поскольку при некорректной постановке задачи количество итераций может стать излишне большим, в программе предусмотрено прекращение итерационного процесса при превышении заранее заданного предельного числа итераций.
program SLAU2; {Решение системы методом Гаусса-Зейделя}
label 1,2,3;
const n=3;
var a:array [1..n,1..n] of real;
b,x:array [1..n] of real;
i,j,k,m:integer;
e,s,d,d1,c:real;
begin
{Ввод исходных данных}
for i:=1 to n do
begin
writeln (‘Введите коэффициенты уравнения’,i);
for j:=1 to n do read (a[i,j]);
writeln (‘Введите свободный член уравнения’,i);
readln (b[i]);
end;
writeln ('Введите точность');readln (e);
writeln ('Введите допустимое кол-во итераций');readln (m);
for i:=2 to n do x[i]:=0;
{Решение системы}
k:=1;
repeat
d1:=0;
for i:=1 to n do
begin
s:=0;
for j:=1 to n do
begin
if i=j then goto 1;
s:=s+a[i,j]*x[j];
1: end;
c:=(b[i]-s)/a[i,i];
d:=abs(c-x[i]);
if d1<d then d1:=d;
x[i]:=c;
end;
k:=k+1;
if k>m then goto 2;
until d1<e;
{Вывод результатов}
writeln (‘решение системы’);
for i:=1 to n do write (x[i]:8:4);
writeln; goto 3;