2.6. Достаточное условие сходимости метода простой итерации.

2.6.Достаточное условие сходимости метода простой итерации

2.6. Достаточное условие сходимости метода простой итерации.

Пустьфункция (x)определена и диффе­ренцируемана отрезке [a,b],причемвсе ее зна­чения (x)[a,b].

Тогда,если выполняется условие

 '(x)< 1

приa< x < b, то:

1)процесс итерации xn= (xn-1) (n=1,2,…)сходится независимо от начальногозначения x0[a,b];

2)предельноезначение является единственным корнем уравненияx= (x)наотрезке [a,b].

Еслиэто условие выполняется не на всеминтервале, то метод может как сходиться,так и расходиться.

Вывод условия сходимости:

Таккак = ()иxn= (xn-1),томожно записать

Потеореме о среднем (она утверждает, чтоесли производная функции f(x)непрерывна на некотором интервале[a,b],то тангенс угла наклона хорды, проведенноймежду точками aиb(т.е.

{f(b)-f(a)/(b-a)}равенпроизводной функции в некоторойпромежуточной точке, лежащей между aиb)частноев последнем выражении будет равно '(C),гдеС— некоторая промежуточная точка винтервале поиска корня.

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

xn= ' (C) (xn-1)

Есливвести обозначение M= max' (x)для всего интервала поиска, то предыдущееравенство может быть переписано в виде:

xnM xn-1

Аналогично

xn-1M xn-2

Тогдадля xnбудет справедливо неравенство:

xnM2xn-2

ит.д.

Продолжаяэти выкладки дальше, в результатеполучаем

xnMnx0

гдеn— натуральноечисло.

Чтобыметод сходился, необходимо выполнениенеравенства:

xn< Mnx0

Отсюдаследует, что M= max' (x)должнобыть меньше единицы.

Всвою очередь, для всех остальных значений' (x)меньших М,можно записать:

'(x)< 1

2.7.Оценка погрешности n-приближения

Методхорд:|x*-xn|(M1-m1)|xn- xn-1|/m1,гдеM1,m1-наибольшееи наименьшее значение |f’(x)|на [a,b].

МетодНьютона:|x*-xn|M2(xn- xn-1)2/2m1,гдеM2-наибольшеезначение |f’’(x)|,m1-наименьшее значение |f’(x)|на [a,b].

Методитераций: Пусть - точное значение корня уравнения х =(x),а число qопределяетсяиз соотношения '(x)q < 1. Тогдасправедливо соотношение (вывод см.ниже):

.

Еслипоставить условие, что истинное значениекорня должно отличаться от приближенногозначения на величину ,т.е. - xn,топриближения x0,x1,… , xnнадовычислять до тех пор, пока не будетвыполнено неравенство

или

итогда = xn

Линейнаясистема nуравнений может быть записана в виде:

a11x1+ a12x2+ … + a1nxn= b1

a21x1+ a22x2+…+ a2nxn= b2

. . . . . . . . . . .

an1x1+ an2x2+ … + annxn= bn

Этусистему линейных уравнений можно такжезаписать в матричном виде:

,

гдеA — матрица коэффициентов системы, а и- вектор-столбец неизвестных ивектор-столбец правых частей соответственно.

.

3.1.2.Классификация слау

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

2.Если система имеет хотя бы одно решение,она называется совместной.Система, не имеющая решений, называетсянесовместной.

3.Совместная система, имеющая единственноерешение, называется определенной.Совместная система, имеющая бесконечноеколичество решений, называетсянеопределенной.

4.Если все коэффициенты правых частейсистемы равны нулю, то система называетсяоднородной.Если хотя бы один из этих коэффициентовне равен нулю, то система называетсянеоднородной.

Однороднаясистема уравнений всегда совместна,т.к. имеет хотя бы одно решение, xi= 0 (i=1,2,…,n),называемое тривиальным.

Источник: https://studfile.net/preview/358638/page:4/

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

2.6. Достаточное условие сходимости метода простой итерации.

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

, .

Неравенство будет справедливо, если диагональные элементы системы удовлетворяют условию:

, .

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

Пример. Решить систему уравнений методом итераций с точностью = 0.005.

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

Переставив уравнения так, чтобы по диагонали стояли преобладающие элементы, получим:

Условия сходимости для коэффициентов преобразованной системы выполняются, т. к. ; ; .

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

Выберем начальные приближения ; ; , тогда:

Дальнейшие итерации дадут значения приближений: ,

,

.

Последнее приближение можно считать решением системы с точностью = 0.005, т. к. .

Рис. 3.1 – Блок-схема. Метод простых итераций

Программа

procedure iteracii;

var

s,y: real;

i,j: integer;

bool: boolean;

x: array[1..k] of real;

t: array[1..k] of real;

xn: array[1..k] of real;

begin

for i:=1 to k do

begin

x[i]:=b[i];

end;

repeat

for i:=1 to k do

begin

s:=0;

for j:=1 to k do

begin

s:=s+a[i,j]*x[j]

end;

xn[i]:=(b[i]-s)/a[i,i]+x[i];

end;

for i:=1 to k do

begin

t[i]:=abs(xn[i]-x[i]);

x[i]:=xn[i];

end;

bool:=true;

i:=1;

while (i=e then

bool:=false;

i:=i+1;

end

until bool=true;

for i:=1 to k do

begin

writeln('X',i,'=',xn[i]);

end;

end;

3.2. Метод Зейделя

Этот метод является уточнённым методом итераций и носит название модифицированного метода итераций.

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

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

,

где .

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

Рис. 3.2 – Блок-схема. Метод Зейделя

Программа

procedure zeydel;

var

s,y: real; i,j: integer; bool: boolean;

x: array[1..k] of real; t: array[1..k] of real; xn: array[1..k] of real;

begin writeln('Method zeydela: ');

for i:=1 to k do

begin x[i]:=b[i]; end;

repeat

for i:=1 to k do

begin s:=0;

for j:=1 to k do

begin s:=s+a[i,j]*x[j]; end;

xn[i]:=(b[i]-s)/a[i,i]+x[i];

t[i]:=abs(xn[i]-x[i]); x[i]:=xn[i];

end;

bool:=true; i:=1;

while (i=e then bool:=false;

i:=i+1;

end

until bool=true;

for i:=1 to k do

begin

writeln('X',i,'=',x[i]);

end;

end;

3.3. Метод Крамера

Алгоритм обладает высокой точностью, но не отличается относительно высокой скоростью, так как для решения системы из N уравнений требуется нахождение N + 1 детерминантов. В данной реализации алгоритма используется метод Гаусса для поиска детерминантов, что хуже, чем если бы метод Гаусса напрямую использовался для решения системы уравнений.

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

.

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

Рис. 3.3 – Блок-схема. Метод Крамера

Программа

procedure kramer;

var u,i: integer;

opredel,opr,r: real;

znak: integer;

begin

fillin;

{Pivedenie k treugolnomu vidu}

triangle(opr,znak);

r:=1;

for u:=1 to k do

r:=r*matrix[u,u];

opredel:=r/opr*znak;

if (opredel0) then

begin

for i:=1 to k do

begin

{perestanoa kolonki i}

fillin;

for u:=1 to k do

begin

if i1 then

matrix[u,i-1]:=a[u,i-1];

matrix[u,i]:=b[u];

end;

triangle(opr,znak);

r:=1;

for u:=1 to k do

r:=r*matrix[u,u];

if (r0) then

writeln('X',i,'= ',r/(opr*opredel)*znak)

else

writeln('X',i,'= ','Unknown');

end;

end

else

writeln('Systema imeet mnojestvo resheniy.');

end;

3.4. Метод Гаусса

Данный метод решения СЛАУ является классичесиким. Он обладает высокой точностью и скоростью, так как основан на элементарных преобразованиях.

Пусть имеется система уравнений:

.

Составим из этой системы матрицу:

.

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

.

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

Рис. 3.4 – Блок-схема. Метод Гаусса

Программа

procedure gauss;

var

u,i: integer;

tmp: real; {for compatability}

begin

fillin;

{Pivedenie k treugolnomu vidu}

triangle(tmp,i);

{nahojdenie korney uravneniya}

if (matrix[k,k]0) then

begin

smatrix[k]:=matrix[k,k+1]/matrix[k,k];

writeln('X',k,'= ',smatrix[k]);

for u:=k-1 downto 1 do

begin

i:=u;

while ik+1 do

begin

smatrix[u]:=smatrix[u]+smatrix[i]*matrix[u,i];

i:=i+1;

end;

smatrix[u]:=(matrix[u,k+1]-smatrix[u])/matrix[u,u];

writeln('X',u,'= ',smatrix[u]);

end;

end

else

writeln('Systema imeet mnojestvo resheniy');

end;

3.5. Дополнения к разделу

Источник: https://infopedia.su/1x6cd1.html

Глава 6 итерациональные методы решения линейных алгебраических систем

2.6. Достаточное условие сходимости метода простой итерации.

⇐ Предыдущая14151617181920212223Следующая ⇒

МЕТОД ПРОСТЫХ ИТЕРАЦИЙ

Рассмотрим систему вида

, (6.1)

где – матрица, а и – -мерные векторы-столбцы.

Преобразуем (6.1) к эквивалентной ей системе вида

(6.2)

где и — некоторые новые матрица и вектор соответственно.

Определим последовательность приближений к неподвижной точке рекуррентным равенством

(6.3)

Итерационный процесс (6.3), начинающийся с некоторого вектора , называется методом простых итераций (МПИ).

Условия сходимости МПИ представлены в следующих теоремах.

Теорема 6.1.Необходимым и достаточным условием сходимости метода простых итераций (6.3) при любом начальном векторе к решению системы (6.2) является требование, чтобы все собственные числа матрицы были во модулю меньше 1.

Теорема 6.2.Пусть . Тогда, при любом начальном векторе МПИ (6.3) сходится к единственному решению задачи (6.2) и, при всех , справедливы оценки погрешности:

1. (апостериорная);

2. (априорная).

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

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

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

Отметим, что неравенство будет гарантией выполнения неравенства только в том случае, когда .

Априорная оценка, как правило, грубее апостериорной.

Замечание 6.2. Как установлено выше, сходимость МПИ (6.3) при условии гарантируется при любом начальном векторе . Очевидно, итераций потребуется тем меньше, чем ближе к .Если нет никакой дополнительной информации о решении задачи (6.

2), за х(0) обычно принимают вектор свободных членов системы (6.2) .Мотивация этого может быть такой: матрица «мала», значит вектор «мал», следовательно и вектор не должен сильно отличаться от вектора . При выборе фигурирующая в теореме 6.

2 априорная оценка принимает вид

МЕТОД ЯКОБИ

Рассмотрим один из способов приведения системы (6.1) к виду (6.2).

Представим матрицу системы (6.1) в виде

,

где — диагональная, а и— соответственно левая и правая строго треугольные (т.е. с нулевой диагональю) матрицы. Тогда система (6.1) может быть записана в виде

(6.7)

и если на диагонали исходной матрицы нет нулей, то эквивалентной (6.1) задачей вида (6.2) будет

, (6.8)

т.е. в равенствах (6.2) и (6.3) следует положить

Основанный на таком приведении системы (6.1) к виду (6.2) метод простых итераций (6.3) называют методом Якоби.

В векторно-матричных обозначениях он определяется формулой

(6.9)

Чтобы записать метод Якоби (6.9) решения системы (6.1) в развернутом виде, достаточно заметить, что обратной матрицей к матрице служит диагональная матрица с элементами диагонали . Поэтому представление (6.8) системы (6.1), записанной в виде (6.7), равнозначно выражению «диагональных неизвестных» через остальные:

(6.10)

При этом итерационный процесс имеет вид

(6.9а)

Теорема 6.3.В случае диагонального преобладания в матрице системы (6.1) метод Якоби (6.9) сходится.

Замечание 6.3. К методу Якоби при условии диагонального преобладания в матрице относится полностью заключение теоремы 6.2, а также предыдущие замечания; нужно лишь учесть в них, что матрица определяется с помощью (6.11), а вектор – равенством

.

Теорема 6.4.Метод Якоби (6.9) сходится к решению системы (6.1) в том и только том случае, когда все корни уравнения

по модулю меньше единицы.

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

.

Последнее же эквивалентно уравнению

,

которое в записи через элементы исходной матрицы и фигурирует в формулировке теоремы.

МЕТОД ЗЕЙДЕЛЯ

Под методом Зейделя обычно понимается такое видоизменение метода простых итераций (6.3) решения СЛАУ, приведенных к виду (6.2), при котором для подсчета -й компоненты -го приближения к искомому вектору используются уже найденные на этом, т.е.

-м шаге, новые значения первых компонент. Это означает, что если система (6.1) тем или иным способом сведена к системе (6.

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

(6.12)

где , a – компоненты заданного (выбранного) начального вектора .

Остановимся подробнее на случае, когда приведение системы (6.1) к виду (6.2) основано на представлении (6.7), т. е. когда метод Зейделя есть модификация метода Якоби. Запись соответствующих расчетных формул здесь сводится к верхней индексации системы (6.10) по типу (6.12):

(6.13)

где ; задается.

Для анализа сходимости метода Зейделя (6.13) обратимся к его векторно-матричной форме. Легко видеть, что если неявный вид метода Якоби, вытекающий из представления (6.7) системы (6.1), есть

(сравните с (6.9)),

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

.

Следовательно, тот же вектор ,который фигурирует в левой части совокупности равенств (6.13), может быть получен по формуле

(6.14)

Последнее выражение определяет не что иное, как МПИ (6.3) для системы вида (6.2), где

,

т. е. результат применения одного шага метода Зейделя (6.13), полученного на основе – разложения матрицы ,можно расценивать, как шаг МПИ для эквивалентной (6.1) задачи о неподвижной точке

(6.15)

(разумеется, если треугольная матрица обратима). Эта связь между методом Зейделя и методом простых итераций позволяет легко переформулировать некоторые утверждения о сходимости МПИ применительно к методу Зейделя (6.13).

Теорема 6.5.Для сходимости метода Зейделя (6.13) необходимо и достаточно, чтобы все корни уравнения

(6.16)

были по модулю меньше единицы.

Прямым следствием теоремы 6.2 для метода Зейделя (6.13) является следующая теорема.

Теорема 6.6.Пусть . Тогда при любом начальном векторе метод Зейделя (6.13) сходится к решению системы (6.1) и справедливы оценки погрешности

(6.17)

Ясно, что для непосредственного использования оценок (6.17) нужно предварительно выполнить обращение треугольной матрицы и перемножить матрицы и . В таком случае частично теряется смысл в поэлементной реализации метода Зейделя (6.

13);вместо этого можно проводить итерации по формуле (6.14) до тех пор, пока не выполнится условие , где – требуемая точность.

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

Более подходящие для использования оценки погрешности метода Зейделя (6.13) можно получить, разлагая матрицу (см. (6.11)) в сумму двух строго треугольных матриц, т.е. полагая

,

где

,

.

С ними эквивалентное (6.1) уравнение (6.2) приобретает вид

,

т.е. для решения будет точным равенство

,

а метод Зейделя (6.13) – соответственно

.

Из двух последних равенств получаем следующее:

.

Это равенство, записанное в виде

(6.18)

можно расценивать как точную связь между погрешностями -го и -го приближений в методе Зейделя (6.13). Отсюда, переходя к нормам, легко вывести априорную оценку погрешности, что можно оформить в виде следующего утверждения.

Теорема 6.7.Пусть . Тогда метод Зейделя (6.13) определяет сходящуюся последовательностьпри любом начальном векторе , и имеет место оценка

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

Ценность ее скорее в том, что в ней фигурирует легко вычисляемый коэффициент связи ошибок результатов двух соседних итерационных шагов, характеризующий быстроту сходимости метода Зейделя (6.13).

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

Теорема 6.8.Пусть , (где матрица (6.11)). Тогда для определяемой методом Зейделя (6.13) последовательности приближений справедлива апостериорная оценка погрешности

.

Из теоремы 6.8 вытекает следующая, более удобная на практике, формулировка.

Следствие 6.1.Пусть – первое из натуральных чисел k, с которым при заданномдля генерируемой процессом Зейделя (6.13) последовательности векторовнекоторых согласованных нормах выполняется равенство

.

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

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

Теорема 6.9.Если в матрицесистемы (6.1)имеет место диагональное преобладание, то метод Зейделя (6.13) сходится, причем быстрее, чем метод Якоби (6.9а).

Замечание 6.4. В соответствии с последней теоремой в методе Зейделя (6.13) вместо оценок (6.17), требующих дополнительных затрат на обращение треугольной матрицы, допустимо использование оценок погрешности метода Якоби. Естественно, они заведомо грубее.

Остановимся еще на одном важном для приложений классе систем вида (6.1), для которых имеет место сходимость метода Зейделя(6.13).

Определение (6.1). Системаназывается нормальной,если матрицасимметричная положительно определенная.

Теорема 6.10.Если система (6.1) – нормальная, то метод Зейделя (6.13) сходится.

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

Теорема 6.11. Пусть.Тогда системанормальная.

Таким образом, если, например, известно, что система (6.1) однозначно разрешима, но в ее матрице коэффициентов нет диагонального преобладания, метод Зейделя типа (6.13) можно применять к системе .

Правда, здесь возникают трудности со своевременным окончанием процесса итерирования, обеспечивающим заданную точность приближенного решения, так как приведенные ранее оценки погрешности (см. теорему 6.6 и замечание 6.7) в этом случае часто «не работают».

Да и сходимость при этом может оказаться весьма медленной.

Наряду с рассмотренными, применяют и другие способы приведения систем (6.1) к виду (6.2) для их решения методами простых итераций и Зейделя. Достаточно общий подход к этой процедуре заключается в том, что эквивалентное (6.1) уравнение умножается на некоторую неособенную матрицу (матричный параметр) и к обеим частям прибавляется вектор х. Полученное уравнение

,

переписанное в виде

,

имеет структуру (6.2). Проблема теперь заключается в подборе матрицы такой, чтобы матрица обладала нужными свойствами для сходимости применяемых методов; для некоторых классов матриц имеются определенные рекомендации.

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

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

⇐ Предыдущая14151617181920212223Следующая ⇒

Дата добавления: 2016-11-12; просмотров: 733 | Нарушение авторских прав | Изречения для студентов

Источник: https://lektsii.org/9-30309.html

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

2.6. Достаточное условие сходимости метода простой итерации.

Рассмотрим уравнение с отделенным корнем X[a, b].Для решения уравнения (2.1)методом простой итерации приведем его к равносильному виду: Это всегда можно сделать, причем многими способами. Например:x=g(x) · f(x) + x φ(x), где g(x) — произвольная непрерывная функция, не имеющая корней на отрезке [a,b].

Пусть x(0) — полученное каким-либо способом приближение к корню x (в простейшем случае x(0)=(a+b)/2).Метод простой итерации заключается в последовательном вычислении членов итерационной последовательности:

(2.3)

x(k+1)=φ(x(k)), k=0, 1, 2, …

начиная с приближения x(0).

УТВЕРЖДЕНИЕ 2.1 Если последовательность {x(k)} метода простой итерации сходитсяи функция φ непрерывна, то предел последовательности является корнем уравнения x=φ(x)

ДОКАЗАТЕЛЬСТВО: Пусть

(2.4)

Перейдем к пределу в равенстве x(k+1)=φ(x(k))Получим с одной сторонv по (2.4), чтоа с другой стороны в силу непрерывности функции φи (2.4)

В результате получаем x*=φ(x*). Следовательно, x* — корень уравнения(2.2), т.е. X=x*

Чтобы пользоваться этим утверждением нужна сходимость последовательности {x(k)}.Достаточное условие сходимости дает:

ТЕОРЕМА 2.1 (о сходимости)Пусть уравнение x=φ(x) имеет единственный корень на отрезке [a,b]и выполнены условия:

1) φ(x)C1[a,b];

2) φ(x)[a,b] x [a,b];

3) существует константа q > 0: | φ '(x) | ≤ q< 1 x [a,b]. Tогда итерационная последовательность {x(k)}, заданная формулой x(k+1) = φ(x(k)), k=0, 1, … сходится при любом начальном приближении x(0)[a,b].

ДОКАЗАТЕЛЬСТВОРассмотрим два соседних члена последовательности {x(k)}: x(k) = φ(x(k-1)) и x(k+1) = φ(x(k))Tак как по условию 2) x(k) и x(k+1)лежат внутри отрезка [a,b], то используя теорему Лагранжа о средних значенияхполучаем:

x (k+1) — x (k) = φ(x (k)) — φ(x (k-1)) = φ '(c k )(x (k) — x (k-1))

где c k (x (k-1), x (k)).

Отсюда получаем:

(2.5)

| x (k+1) — x (k) | = | φ '(c k ) | · | x (k) — x (k-1) | ≤ q | x (k) — x (k-1)| ≤
≤ q ( q | x (k-1) — x (k-2) | ) = q 2 | x (k-1) — x (k-2) |
≤ … ≤ q k | x (1) — x (0) |

Рассмотрим ряд

(2.6)

S∞ = x (0) + ( x (1) — x (0) ) + … + ( x (k+1) — x (k) ) + … .

Если мы докажем, что этот ряд сходится, то значит сходитсяи последовательность его частичных сумм
Sk = x (0) + ( x (1) — x (0) ) + … + ( x (k) — x (k-1) ).

Но нетрудно вычислить, что

Следовательно, мы тем самым докажем и сходимость итерационной последовательности {x(k)}.

Для доказательства сходимости pяда (2.6) сравним его почленно (без первого слагаемого x(0)) с рядом

(2.8)

q 0 | x (1) — x (0) | + q 1 |x (1) — x (0)| + … + |x (1) — x (0)| + …,

который сходится как бесконечно убывающая геометрическая прогрессия(так как по условию q< 1). В силу неравенства (2.5) абсолютные величины ряда (2.6) не превосходят соответствующих членов сходящегося ряда(2.8) (то есть ряд (2.8) мажорирует ряд (2.6). Следовательно ряд (2.6) также сходится. Tем самым сходится последовательность {x(0)}

Получим формулу, дающую способ оценки погрешности |X — x (k+1)| метода простой итерации.

Имеем X — x(k+1) = X — Sk+1 = S∞ — Sk+1 = (x(k+2) — (k+1) ) + (x(k+3) — x(k+2) ) + … . Следовательно |X — x(k+1)| ≤ |x(k+2) — (k+1) | + |x(k+3) — x(k+2) | + … ≤ qk+1 |x(1) — x(0) | + qk+2 |x(1) — x(0) | + … = qk+1|x(1) — x(0) | / (1-q)

В результате получаем формулу

(2.9)

|X — x(k+1)| ≤ qk+1|x(1) — x(0) | / (1-q)

Взяв за x(0) значение x(k), за x(1) — значение x(k+1) (так как при выполнении условий теоремы такой выбор возможен)и учитывая, что при имеет место неравенство qk+1q выводим:

|X — x(k+1)| ≤ qk+1|x(k+1) — x(k) | / (1-q) ≤ q|x(k+1) — x(k) | / (1-q)

Итак, окончательно получаем:

(2.10)

|X — x(k+1)| ≤ q|x(k+1) — x(k) | / (1-q)

Используем эту формулу для вывода критерия окончания итерационной последовательности.Пусть уравнение x=φ(x)решается методом простой итерации, причем ответ должен быть найден с точностью ε , то есть |X — x(k+1)| ≤ ε. С учетом (2.10) получаем, чтоточность ε будет достигнута, если выполнено неравенство

(2.11)

|x(k+1)-x(k)|(1-q)/q

Tаким образом для нахождения корней уравнения x=φ(x) методом простой итерации с точностью нужно продолжать итерации до тех пор, пока модуль разности между последними соседними приближениями остается больше числа ε(1-q)/q.

ЗАМЕЧАНИЕ 2.2 В качестве константы q обычно берут оценку сверху для величины

ПРИМЕР 2.1 Составим последовательность для решения уравнения f(x)=x·ex=0 по методу простой итерации.

Приведем уравнение к итерационному виду:

x = e — x ≡ φ(x).

Далее графически произведем отделение корня.

Несложный анализ графика показывает, что корень X[e-1,1]. Tак как при x[e-1,1] и e-x[e-1,1] , x[e-1,1], то в соответствии с теоремой итерационная последовательность x(k+1) = e — x(k), k=0, 1, 2, … гарантированно сходится к корню уравнения. В качестве начального приближения к корню можно взять x(0)=0.5(1+e-1).

Источник: http://e-lib.gasu.ru/eposobia/metody/R_2_2.html

Условие сходимости метода простых итераций

2.6. Достаточное условие сходимости метода простой итерации.

Понятие«вычислительная задача». Типы вычислительных задач и их постановка.

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

Вычислительные задачи связаны с вычислением в традиционном (арифметическом) смысле этого слова неизвестного значения информационного объекта (переменной, функции и т.д.).

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

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

Условия корректности вычислительной задачи.

Корректность. Определим вначале понятие устойчивости решения.

Решение задачи y* называется устойчивым по исходным данным x*, если оно зависит от исходных данных непрерывным образом.

Это означает, что малому изменению исходных данных соответствует малое изменение решения.

Строго говоря, для любого e > 0 существует d = d(e) > 0 такое, что всякому исходному данному x*, удовлетворяющему условию |x — x*| < d, соответствует приближенное решение y*, для которого |y – y*| < e.

Говорят, что задача поставлена корректно, если выполнены следующие три условия:

1. Решение существует при любых допустимых исходных данных.

2. Это решение единственно.

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

Если хотя бы одно из этих условий не выполнено, задача называется некорректной.

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

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

Решение по этому методу выполняется в два хода: прямой и обратный.

При прямом ходе исходная система уравнений:

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

При обратном – из эквивалентной системы идёт последовательное, начиная с конца, определение неизвестных xj, j= n, n – 1, …, 1 по следующим рекуррентным формулам:

– при j= n получаем

– при j=n – 1, n – 2, … , 1 получаем

Трудоёмкость метода Гаусса

Количество действий прямого хода:

Количество действий обратного хода:

.

Суммарное количество действий:

Здесь n – количество уравнений (порядок) системы.

При n = 3

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

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

Имеем исходную систему уравнений:

           (1.5)

Запишем систему (1.5) в матричной форме:

AX = B,                                                  

где A (n´n) – матрица коэффициентов aij;

B(n) – вектор правых частей bi;

X(n) – вектор решений xj.

Можно представить исходную систему матричным уравнением

AXB = 0                                             

или в развёрнутой матричной форме

Вектор-столбец в правой части с нулевыми значениями элементов получается, когда векторX есть точное решение системы. В противном случае получим вектор-«невязок»

Обозначим через Z вектор приближённых значений решения системы. Вначале это будет нулевое приближение – вектор Z(0). В качестве начального приближения решения системы можно брать .

При подстановке в систему (1.8) на место X вектора Z(0) получим:

                (1.9)

где  – вектор-«невязок» начального (нулевого) приближения относительно точного решения.

Цель и суть метода простых итераций – сведение к нулю «невязок» в решении системы (1.9). Практически стремятся к выполнению условия

где S – номер итерации, S = 0, 1, 2, …

Общая формула

 где j – номер слагаемого скалярного произведения i-той строки матрицы A на вектор Z.

Условие сходимости метода простых итераций

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

Дата добавления: 2018-04-15; просмотров: 670;

Источник: https://studopedia.net/4_11098_uslovie-shodimosti-metoda-prostih-iteratsiy.html

Uchebnik-free
Добавить комментарий