Численные методы решения типовых математических задач (стр. 2 из 8)

откуда

Продолжая этот процесс, получим из i-го уравнения СЛАУ (1.1):

следовательно

Из последнего уравнения СЛАУ имеем

то есть

Метод простых итераций

При большом числе уравнений прямые методы решения СЛАУ (за исключением метода прогонки) становятся труднореализуемыми на ЭВМ прежде всего из-за сложности хранения и обработки матриц большой размерности. В то же время характерной особенностью ряда часто встречающихся в прикладных задачах СЛАУ является разреженность матриц. Число ненулевых элементов таких матриц мало по сравнению с их размерностью. Для решения СЛАУ с разреженными матрицами предпочтительнее использовать итерационные методы.

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

Метод Зейделя решения СЛАУ

Метод простых итераций довольно медленно сходится. Для его ускорения существует метод Зейделя, заключающийся в том, что при вычислении компонента xik+1 вектора неизвестных на (k+1)-й итерации используются x1k+1, x2k+1, .., xik+1 уже вычисленные на (k+1)-й итерации. Значения остальных компонент берутся из предыдущей итерации. Так же как и в методе простых итераций строится эквивалентная СЛАУ и за начальное приближение принимается вектор правых частей . Тогда метод Зейделя для известного вектора на k-ой итерации имеет вид:

предыдущей итерации. Так же как и в методе простых итераций строится эквивалентная СЛАУ и за начальное приближение принимается вектор правых частей . Тогда метод Зейделя для известного вектора на k-ой итерации имеет вид:

Из этой системы видно, что

, где В - нижняя треугольная матрица с диагональными элементами , равными нулю, а С - верхняя треугольная матрица с диагональными элементами, отличными от нуля, α=B+C. Следовательно

При таком способе приведения исходной СЛАУ к эквивалентному виду метод простых итераций носит название метода Якоби.

откуда

Таким образом, метод Зейделя является методом простых итераций с матрицей правых частей α=(E-B)-1C и вектором правых частей (E-B)-1β.

Разрешим систему относительно неизвестных при ненулевых диагональных элементах , aii≠0, i= 1,n (если какой-либо коэффициент на главной диагонали равен нулю, достаточно соответствующее уравнение поменять местами с любым другим уравнением). Получим следующие выражения для компонентов вектора β и матрицы α эквивалентной системы

В качестве нулевого приближения x⁽⁰⁾ вектора неизвестных примем вектор правых частей x⁽⁰⁾=β. Тогда метод простых итераций примет вид:

Из (1.19) видно преимущество итерационных методов по сравнению, например, с рассмотренным выше методом Гаусса. В вычислительном процессе участвуют только произведения матрицы на вектор, что позволяет работать только с ненулевыми элементами матрицы, значительно упрощая процесс хранения и обработки матриц.

Имеет место следующее достаточное условие сходимости метода простых итераций.

Метод простых итераций (1.19) сходится к единственному решению СЛАУ при любом начальном приближении x⁽⁰⁾, если какая-либо норма матрицы α эквивалентной системы меньше единицы

Если используется метод Якоби (выражения (1.18) для эквивалентной СЛАУ), то

достаточным условием сходимости является диагональное преобладание матрицы A, т.е.

(для каждой строки матрицы A модули элементов, стоящих на главной диагонали, больше суммы модулей недиагональных элементов). Очевидно, что в этом случае ||α||_c меньше единицы и, следовательно, итерационный процесс (1.19) сходится.

Приведем также необходимое и достаточное условие сходимости метода простых итераций. Для сходимости итерационного процесса (1.19) необходимо и достаточно, чтобы спектр матрицы α эквивалентной системы лежал внутри круга с радиусом, равным единице.

При выполнении достаточного условия сходимости оценка погрешности решения на k- ой итерации дается выражением:

Следует подчеркнуть, что это неравенство дает завышенное число итераций k, поэтому редко используется на практике

1.4 Численный метод решения задачи

Разрешим систему относительно неизвестных при ненулевых диагональных элементах , aii≠0, i= 1,n (если какой-либо коэффициент на главной диагонали равен нулю, достаточно соответствующее уравнение поменять местами с любым другим уравнением). Получим следующие выражения для компонентов вектора β и матрицы α эквивалентной системы:

При таком способе приведения исходной СЛАУ к эквивалентному виду метод простых итераций носит название метода Якоби.

В качестве нулевого приближения x⁽⁰⁾ вектора неизвестных примем вектор правых частей x⁽⁰⁾=β. Тогда метод простых итераций примет вид:

Из (1.19) видно преимущество итерационных методов по сравнению, например, с рассмотренным выше методом Гаусса. В вычислительном процессе участвуют только произведения матрицы на вектор, что позволяет работать только с ненулевыми элементами матрицы, значительно упрощая процесс хранения и обработки матриц.

Имеет место следующее достаточное условие сходимости метода простых итераций.

Метод простых итераций (1.19) сходится к единственному решению СЛАУ при любом начальном приближении x⁽⁰⁾, если какая-либо норма матрицы α эквивалентной системы меньше единицы

Если используется метод Якоби (выражения (1.18) для эквивалентной СЛАУ), то

достаточным условием сходимости является диагональное преобладание матрицы A, т.е.

(для каждой строки матрицы A модули элементов, стоящих на главной диагонали, больше суммы модулей недиагональных элементов). Очевидно, что в этом случае ||α||_c меньше единицы и, следовательно, итерационный процесс (1.19) сходится.

Приведем также необходимое и достаточное условие сходимости метода простых итераций. Для сходимости итерационного процесса (1.19) необходимо и достаточно, чтобы спектр матрицы α эквивалентной системы лежал внутри круга с радиусом, равным единице.

При выполнении достаточного условия сходимости оценка погрешности решения на k- ой итерации дается выражением:

где x^·- точное решение СЛАУ.

Процесс итераций останавливается при выполнении условия , где εε≤)(kε - задаваемая вычислителем точность.

Принимая во внимание, что из (1.20) следует неравенство

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

откуда получаем априорную оценку числа итераций k при ||α||<1

Следует подчеркнуть, что это неравенство дает завышенное число итераций k, поэтому редко используется на практике.

1.6 Текст программы

program Yakobi;

uses crt;

const

maxn=100;

type

matrix=array[1..maxn,1..maxn] of real;

vector=array[1..maxn] of real;

vector1=array[1..maxn] of real;

var

i,j,n,k1: integer;

e,norma:real;

a: matrix;

b: vector;

x2,x3: vector1;

imya,dannble_i_rezultat,ekran:string;

procedure input(var kolvo:integer; var pogreshnostb:real; var matr1:matrix; var matr2:vector);

{Ввод исходных данных}

var i,j,code:integer;

a_s: string;

b_s: string;

begin

writeln('введите количество уравнений');

readln(kolvo);

writeln('введите погрешность вычисления');

readln(pogreshnostb);

writeln('введите матрицу коэффициентов при неизвестных');

for i:=1 to kolvo do

for j:=1 to kolvo do

begin

repeat

begin

writeln('введите элемент [',i,',',j,'] и нажмите Enter');

readln(a_s);

if (i=j) and (a_s='0') then

repeat

begin

writeln('Элементы на главной диагонали должны быть отличны от нуля. Повторите ввод');

readln(a_s);

end;

until a_s<>'0';

val(a_s,matr1[i,j],code);

end;

until code=0;

end;

writeln('введите вектор свободных коэффициентов');

for j:=1 to kolvo do

begin

repeat

writeln('введите элемент ',j,' и нажмите Enter');