Алгоритм решения системы 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.3x4x2 = -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 Следовательно, процесс итерации для системы (5.22) сходится.За начальное приближение корня примем: 0x(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 отсюда 0.55k+1 т.е. –(k+1)∙0.25964 k+1 > 4.58983/0.25964 ≈ 17.7 и k > 16.7 можно принять k=17.Следует отметить, что теоретически оценка числа итераций, необходимых для обеспечения заданой точности, практически оказывается весьма завышенной.Большое число научно-технических задач, а также некоторые исследования в области выч. лог-ки требует нахождения собств. значений и собств. векторов матриц. Однако эти вопросы остаются за рамками курса.^ Нелинейные уравненияУравнения с одним неизвестным: Задача нахождения корней нелинейного уравнения вида F(x)=0 (6.1)встречается в различных областях научных исследований (здесь F(x) – некоторая непрерывная функция). Нелинейные уравнения можно разделить на 2 класса – алгебраические и трансцендентные. Алгебраическими называются уравнения содержащие только алгебраические функции (целые, рациональные, иррациональные). В частности, мн-н является целой целой алгебраической функцией. Уравнения содержащие другие функции (тригонометрические, показательные, логарифмические и д.р.) называются трансцендентными. Методы решения нелинейных уравнений делятся на прямые и итерационные. Прямые методы позволяют записывать корни в виде некоторого конечного соотношения(формулы). Однако встречающиеся на практике уравнения не удается решить такими простыми методами. Для их решения используют итерационные методы, т.е. методы последовательных приближений. Как и в случаях СЛАУ, алгоритм нахождения корня нелинейного уравнения с помощью итерационного метода состоит из двух этапов:Нахождение приближенного значения корня(начального приближения)Уточнение приближенного значения до некоторой заданной степени точности. В некоторых методах отыскивается не начальное приближение, а некоторый отрезок, содержащий корень. Начальное приближение может быть найдено различными способами: из физических соображений, из решения аналитической задачи при других исходных данных, с помощью графических методов.Если такие алгоритмы оценки исходного приближения провести не удается, то находят две близко расположенные очки a и b, в которых непрерывная функция F(x) принимает значения разных знаков, т.е. F(a)∙ F(b)В качестве начального приближения 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|Взяв в качестве приближения решения к-е приближение корня x*=ck, с учетом обозначения x=c (6.4) запишем в виде:|c-ck|Из (6.2) следует, что (6.5) выполнено, если bk-akТ.о. мы получим условие, до выполнения которого необходимо продолжать итерационный процесс. Метод деления отрезка пополам всегда сходится(в отличие от большинства других методов), причем можно гарантировать, что полученное решение будет иметь наперед заданную точность (в рамках разрядности компьютера).однако метод бисекции довольно медленный. Вычислим число итераций требуемое для достижения точности ε.Пользуясь (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)| ^ Алгоритм итерац. процесса нахождения корня уравнения методом деления отрезка пополам.ввод a, b, ε вычисление F(а)пока b-a ≥ 2ε c=(a+b)/2 вычисление F(c) да нетF(a)· F(c)>0a=cb=cc=(a+b)/2 вывод сМетод хорд (У Пирумова: метод секущих)Пусть мы нашли [a, b], на котором функция F(х) меняет знак. Для определения примемF(а) > 0, F(b) В данном методе процесс итераций состоит в том, что в качестве приближения корню уравнения (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, b] отбрасываем. Следующая итерация состоит в определении нового приближения с1 как точки пересечения хорды АВ1 с осью абсцисс и т.д. Здесь условие окончания итераций типа (6.6) неприменимо. На рисунке хорошо видно, что длина [а, сk] никогда не станет меньше длины [а, с]. Здесь нужно использовать условие близости двух последовательных приближений:|ck-ck-1|Или условие малости невязки (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)с1=с0-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Очевидно, итерации расходятся. Для предотвращения расходимости иногда целесообразно использовать смешанный алгоритм: сначала применяется всегда сходится метод(напр. метод деления отрезка пополам), а после некоторого числа итераций – быстро сх-ся м-д Ньютона.