Оценка погрешности приближений процесса итерации



Скачать 94.14 Kb.
Дата03.06.2013
Размер94.14 Kb.
ТипДокументы
Алгоритм решения системы n линейных уравнений методом Гаусса- Зейделя представлен в книге Турчак, Плотников на стр. 130
Оценка погрешности приближений процесса итерации:
Пусть x(k-1) и x(k) (k≥1) – два последовательных приближения решения линейной системы x=αx+β

При р≥1 имеем:

||x(k+p) – x(k)|| ≤ || x(k+p) – x(k)|| + ||x(k+2) – x(k+1)||+…+ |x(k+p) – x(k+p-1)|| (5.18)

т.к. x(m+1)= αx(m)+β и x(m)= αx(m-1)+β,

то x(m+1) - x(m)=α( x(m) - x(m-1) ) и =>

|| x(m+1) - x(m) || ≤ ||α||∙|| x(m) - x(m-1) || ≤ ||α||(m-k) || x(k+1) – x(k) || при m>k≥1

Поэтому из формулы (5.18) получаем

|| x(k+p) – x(k) || ≤ ||x(k+1) – x(k) || + ||α||∙|| x(k+1) - x(k) || +…

…+||α||(p-1) || x(k+1) – x(k) || ≤ 1/(1-||α||) ∙ || x(k+1) – x(k) ||

Переходя в последнем неравенстве к пределу при р→∞, получим окончательно:

|| x – x(k) || ≤ || x(k+1) – x(k) ||/(1-||α||) при k≥1 (5.
19)

или || x – x(k) || ≤ ||α||/(1-||α||)∙|| x(k) – x(k-1) ||

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

|| x – x(k) || ≤ ||α||(k+1)/( 1-||α||)∙||x(1)- x(0)||

В частности, если выбрать x(0)=β, то

x(1)=αβ+β, тогда || x(1)- x(0) || = ||αβ||≤||α||∙||β|| =>

|| x - x(k) || ≤ ||α||(k+1)/(1-||α||)∙||β|| (5.20)
Пример: Показать, что для данной системы процесс итерации сходится. Сколько итераций следует выполнить, чтобы найти корни системы с точностью до 10:-4

Решение:

Исходная система

10x1 – x2 + 2x3 – 3x4 = 0

x1 + 10x2 - x3 – 2x4 = 5

2x1 + 3x2 + 20x3 – x4 = -10

3x1 –2x2 + x3 – 20x4 = 15 (5.21)

Приведем систему к специальному виду:

x1 = 0.1x2 – 0.2x3 + 0.3x4

x2 = -0.1x1 ­+ 0,1x3 – 0.2x4 + 0.5

x3 = -0.1x1 – 0.15x2 + 0.05x4 – 0.5

x4 = -0.15x1 – 0.1x2 – 0.005x3 – 0.75 (5.22)

Отсюда матрица системы:

0 0,1 -0,2 0,3

α= -0,1 0 0,1 -0,2

-0,1 -0,15 0 0,05

-0,15 -0,1 -0,05 0
Используя, например, Lнорму, получим:

||α||L=max(0.35; 0.35; 0.35; 0.55)=0.55 < 1

Следовательно, процесс итерации для системы (5.22) сходится.

За начальное приближение корня примем:

0

x(0)=β= 0.5

-0.5

0.75

Отсюда

||β||L= 0 + 0.5 + 0.5 + 0.75 = 1.75

Пусть k – число итераций, необходимое для достижения заданной точности. Применяя формулу (5.20), получим:

||x-x(k)|| ≤ (||α||L(k+1)∙||β||L)/(1-||α||L) = (0.55k+1∙1.75)/0.45 < 10-4

отсюда 0.55k+1 < 45/175∙10-4 и (k+1)∙lg0.55 < lg45 – lg175 – 4

т.е. –(k+1)∙0.25964 < 1.65321 – 2.24304 – 4 = -4.58983 =>

k+1 > 4.58983/0.25964 ≈ 17.7 и k > 16.7 можно принять k=17.

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

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

Уравнения с одним неизвестным:

Задача нахождения корней нелинейного уравнения вида F(x)=0 (6.1)

встречается в различных областях научных исследований (здесь F(x) – некоторая непрерывная функция). Нелинейные уравнения можно разделить на 2 класса – алгебраические и трансцендентные.

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

Методы решения нелинейных уравнений делятся на прямые и итерационные.

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

  1. Нахождение приближенного значения корня(начального приближения)

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

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

Если такие алгоритмы оценки исходного приближения провести не удается, то находят две близко расположенные очки a и b, в которых непрерывная функция F(x) принимает значения разных знаков, т.е. F(a)∙ F(b)<0. В этом случае между точками a и b по крайней мере одна точка, в которой F(x)=0.

В качестве начального приближения x(0) можно принять середину отрезка

[a, b], т.е. x(0)=(a+b)/2. Общую схему итерац. методов мы уже рассмотрели. Итерац. процесс состоит в последовательном уточнении начального приближения.

Каждый шаг называется итерацией. В результате итераций находится последовательность приближенных значений корня x1, x2,…, xk, …

и если эти значения с ростом k стремятся к истинному значению корня

limk→∞x(k)=x

то говорят, что итерац. процесс сходится. В отличие от случая СЛАУ x(k) скаляр, а не вектор, поэтому пока номер итераций будем обозначать нижний индексом xk.

Рассмотрим некоторые итерационные методы решения трансцендентных уравнений.

Один из простейших методов нахождения корней уравнения нелинейных

уравнений - метод деления отрезка пополам (метод бисекции)

(У Парумова метод дихотомии)

Допустим, нам удалось найти [a, b], на котором расположено искомое значение корня x=c, c [a, b]

Мы будем предполагать, что x=c – единственный корень на [a, b]. В противном случае можно выбрать меньший [ ].

В качестве начального приближения корня принимаем середину этого отрезка c0=a+b / 2. Далее исследуем значения ф-ии F(x) на концах отрезков [a, c0] и [c0, b], т.е. F(a), F(c0), F(b). Тот из отрезков, на конце которого F(x) принимает значения разных знаков, содержит искомый корень. Этот отрезок принимает в качестве нового [a1, b1]. Вторую половину [a, b], на которой знак F(x) не меняется, отбрасываем. В качестве первого приближения корня принимаем середину нового отрезка c1=a1+b1 / 2 и т.д.

Т.о к-е приближение вычисляется так ck=ak+bk / 2(6.2)

После каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, а после «К» итерации он сокращается в 2к раз:

bk-ak=b-a / 2k (6.3)

Пусть приближенное решение x* требуется найти с точностью до некоторого значения числа ε>0:

|х-хk|< ε (6.4)

Взяв в качестве приближения решения к-е приближение корня x*=ck, с учетом обозначения x=c (6.4) запишем в виде:

|c-ck|< ε (6.5)

Из (6.2) следует, что (6.5) выполнено, если bk-ak<2ε (6.6)

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




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

однако метод бисекции довольно медленный. Вычислим число итераций требуемое для достижения точности ε.

Пользуясь (6.3), выясним, для каких k выполнимо условие (6.6), и возьмем наименьшее из таких k. Окончательно получим:

k>log2(b-a/2ε)

N=E(log2(b-a/2ε))+1 (6.7)

Где Е(х) – целая часть числа х. обычно для метода деления отрезка пополам N большее, чем для некоторых других методов, что не является препятствием к применению этого метода, если вычисление значений функции F(x) несложно.

Итерационный процесс можно завершать и тогда, когда значение функции F(x) после kой итерации станет по модулю меньше ε

|F(x)| < ε (6.8)


Алгоритм итерац. процесса нахождения корня уравнения методом деления отрезка пополам.
ввод a, b, ε

вычисление F(а)

пока b-a ≥ 2ε

c=(a+b)/2

вычисление F(c)

да нет

F(a)· F(c)>0


a=c

b=c




c=(a+b)/2

вывод с
Метод хорд (У Пирумова: метод секущих)

Пусть мы нашли [a, b], на котором функция F(х) меняет знак. Для определения примем

F(а) > 0, F(b) < 0


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

Уравнение хорды АВ:

(y-F(а)­­­­)/(F(b)-F(а)) = (х-а/(b-а)

Для точки её пересечение с осью абсцисс (х=с0, y=0) получим уравнение:

с0=а – ((b-а)/(F(b)-F(а))∙F(а) (6.9)

Далее, сравним знаки величин F(а) и F(с0) для рассматриваемого случая, делаем вывод что корень находится в интервале (а, с0), т.к. F(b)∙(а)<0.

Отрезок [с0, b] отбрасываем. Следующая итерация состоит в определении нового приближения с1 как точки пересечения хорды АВ1 с осью абсцисс и т.д. Здесь условие окончания итераций типа (6.6) неприменимо.

На рисунке хорошо видно, что длина [а, сk] никогда не станет меньше длины [а, с].

Здесь нужно использовать условие близости двух последовательных приближений:

|ck-ck-1|<ε (6.10)

Или условие малости невязки (6.8). Метод бисекции и метод хорд похожи, в частности процедурной проверки знаков функции на концах [ ]. При этом метод хорд в ряде случаев дает более быструю сходимость итерационного процесса. Оба метода не требуют знания дополнительной информации о функции F(х), достаточно условия непрерывности F(х).

Более сложный метод решения нелинейного уравнения требует дополнительной информации о функции F(х), например диф-ть.

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

Примером такого метода может быть метод Ньютона(метод касательных).

Отличие от метода хорд, на kой итерации вместо хорды строится касательная к кривой y=F(х) при х=сk-1 и ищется точка пересечения касательной с осью абсцисс. При этом не обязательно задавать [а, b], достаточно лишь найти некоторое начальное приближение корня х=с0.



Уравнение касательной, проведенной к кривой y=F(х) в точке М0 с координатами (с0, F(с0)) имеет вид:

y-F(с0)=F’(с0)(х-с0)

отсюда находим следующее приближение корня с1 как абсциссу точки пересечения касательной с осью х (y=0)

с10-F(с0)/F’(c0)

Аналогично находят следующее приближения как точки пересечения с осью M1, M2… Формула для kго приближения

сk=ck-1-F(ck-1)/F’(ck-1) k=1, 2,… (6.11)

Необходимо, чтобы F’(сk-1)≠0.

Для окончания итерационного процесса можно использовать условия (6.10) или (6.8).

Из (6.11) следует, что объем вычислений на каждой итерации метода Ньютона больше, чем в расмотреных ранее методах, т.к. приходится вычислять F(х) и F’(x). Однако скорость сходимости здесь значительно выше.

Имеет место след теорема:

Пусть х=с – корень уравнения (6.1), т.е. F(с)=0, а F’(с)≠0 и F’’(x) непрерывна.

Тогда существует окрестность D корня с (с є D) такая, что если начальное приближение с0 принадлежит этой окрестности, то для метода Ньютона последовательность приближения {ck} сходится к с при k→∞

При этом для погрешности корня εk=с-сk имеет место соотношение

limk→∞k / ε2k-1| = |F”(c)/2F’(c)|
Трудность применения метода Ньютона состоит в выборе начального приближения, kое должно находиться в окрестности D. При неудачном выборе начального приближения итерации могут расходиться.

Пример:

для уравнения arctg(x)=0 (корень х=с=0) при начальном приближении с0=1.5 первые 6 итераций приводят к погрешностям:

ε1=1.69; ε2=-2.32; ε3=5.11; ε4=-32,3; ε5=1.58∙103; ε6=-3.89∙106

Очевидно, итерации расходятся.

Для предотвращения расходимости иногда целесообразно использовать смешанный алгоритм:

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

Похожие:

Оценка погрешности приближений процесса итерации iconПогрешности измерений
Задачей экспериментатора является не только нахождение самой величины, но и оценка допущенной при измерении погрешности. В зависимости...
Оценка погрешности приближений процесса итерации iconЛекция Погрешности измерений. Тема погрешности измерений. Классификация погрешностей измерений
Систематические погрешности – погрешности постоянные или изменяющиеся по определенному закону в зависимости от вызывающих их причин....
Оценка погрешности приближений процесса итерации iconСписок экзаменационных вопросов по дисциплине «Вычислительный эксперимент»
Абсолютная и относительная погрешности. Их связь. Погрешности арифметических операций. Значащая и верная цифра в позиционной записи...
Оценка погрешности приближений процесса итерации iconFaq: Численные Методы, часть II системы линейных алгебраических уравнений: итерационные методы
Итерационный метод называется одношаговым, если на каждой итерации требуется результат лишь одной предыдущей итерации. Каноническая...
Оценка погрешности приближений процесса итерации iconОценка погрешностей измерений при выполнении лабораторных работ по физике
Погрешности возникают при любых измерениях, и только правильная оценка погрешностей проведенных измерений и расчетов позволяет выяснить...
Оценка погрешности приближений процесса итерации iconИзложение основных приближений и методов современной квантовой химии. Студент должен
Понять сущность основных приближений, используемых при квантово-химическом исследовании атомов, молекул, ионов, молекулярных ассоциатов,...
Оценка погрешности приближений процесса итерации iconВведение в численные методы
Априорная и апостериорная оценка погрешности решения задачи Коши для обыкновенных дифференциальных уравнений
Оценка погрешности приближений процесса итерации iconОценка погрешностей косвенных измерений
Цель работы: на практическом примере научиться проводить косвенные измерения и оценивать их погрешности
Оценка погрешности приближений процесса итерации iconЛекции  32 часа Экзамен  нет практические(семинарские) занятия 
Различные формы интерполяционного многочлена, оценка погрешности интерполяции на отрезке
Оценка погрешности приближений процесса итерации iconУрок по теме «Оценка погрешности»
Абсолютную погрешность приближения можно найти лишь в том случае, когда известны точное и приближенное значения величины
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org