МУ к лабораторным работам (1238837), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Метод простой итерацииПусть известно, что интересующий нас корень x* уравненияF ( x )  0 лежит в интервале Y  {x | a  x  b}. Приведем уравнение F ( x )  0 к равносильному уравнению вида x  f (x ) наинтервале U  Y таком, что a  x  b. Можно положитьf ( x )  x  F ( x),где   const. Такой вариант метода простых итераций иногдатакже называют методом релаксации. Для отыскания решенияx* , принадлежащего интервалу Y, зададим x 0 , а затем вычислим последующие x n по формулеx n 1  f ( x n ),n = 0, 1, 2, …(5.1)Т еор ем а 1. Пусть функция F (x) непрерывна и итерационный процесс (5.1) сходится к значению x* . Тогда x* — корень уравнения F ( x)  0.80Т еор ем а 2.

Пусть функция f (x ) имеет производную вовсех точках области U (т. е. интервала a  x  b ), и пусть существует q, 0  q  1, q  const такое, что || f x ||  q всюду вU. Тогда существует такая окрестность корня, что при любомx 0 из этой окрестности метод простых итераций сходится,причем имеет место оценка:|| x *  x n ||  q n || x *  x 0 ||,n > 0.За м еча ние. Практический смысл теоремы 2 заключается в следующем. Она утверждает, что существует такое достаточно мелкое разбиение U, при котором любая из точек одного из элементов разбиения может быть выбрана как x 0 . При таком выбореначального приближения итерационный процесс с необходимостью сходится.

Таким образом, поиск начального приближения,при котором итерационный процесс сходится, можно передатьмашине. При этом для погрешности  n  x*  x n на каждой итерации выполнена оценка||  n ||  q n ||  0 ||,n = 1, 2, …5.4. Метод НьютонаПусть приближение x n к корню x* уравнения F ( x )  0 уженайдено. Воспользуемся приближенной формулойF ( x)  F ( x n )  Fx  ( x  x n ),точность которой возрастает при приближении x n к x * .

Вместо исходного уравнения F ( x )  0 воспользуемся линейнымуравнениемF ( x n )  Fx ( x n )  ( x  x n )  0.Решение этого уравнения примем за приближение x n 1 :x n 1  x n  [ F x ( x n )] 1  F ( x n ),n = 0, 1, 2, …(5.2)Метод линеаризации Ньютона допускает простую геометрическую интерпретацию (рис. 5). График функции F (x) за-81меняется касательной к нему в точке ( x n , F ( x n )).

За приближение x n 1 принимается точка пересечения полученной прямой с осью абсцисс.Формулу (5.2) можно интерпретировать как метод простойитерации с функцией f ( x)  x  [ Fx ] 1  F ( x ). В точке корня x*уравненияF ( x)  0равенствоf x  0, поэтому нера-выполняетсявенство | f x |  q верно для любогоположительного фиксированногозначения q в достаточно малой окрестности корня.Следовательно, асимптотическипоследовательность погрешРис. 5ностей n  | x*  x n |методаНьютона убывает быстрее последовательности членов геометрической прогрессии. Справедлива теорема о квадратичной сходимости метода Ньютона.Т еор ем а 3.

Пусть функция F (x) задана на интервалеy  r  x  y  r,r0и удовлетворяет следующим условиям:1) F (x) дважды непрерывно дифференцируема на этоминтервале;2) для всех точек интервала F ( x)  0 и существуют конечные значенияM1  sup | [ F ( x)]1 |,M 2  sup | F ( x) |,M 2  0;3) уравнение F ( x )  0 имеет корень :y r  2Mгде M  M1M 2 .82   2M y  r,Тогда для любого значения x 0 :2M x0   2M,итерационный процесс сходится к , причемM | xn   |    2 2n 1n| x 0   |2 .На практике более привлекательна такая формулировка условий сходимости метода Ньютона, для которой не нужна никакая информация о решении уравнения.

Примером формулировки может служить следующая теорема.Т еор ем а 4. Пусть функция F (x) определена и дваждынепрерывно дифференцируема на интервале | x  x 0 |  r (r > 0).Пусть также F ( x 0 )  0,F ( x 0 )  0, существует конечноезначение M  sup | [ F ( x 0 )]1 F ( x) |  0 и2M F (x 0 ) 1,F ( x 0 )2F (x 0 )F ( x 0 ) r.Тогда итерации процесса Ньютона сходятся к некоторому решению уравнения , для погрешности справедлива оценкаF (x 0 )| xn   | 2MF ( x 0 )2 n M 12n.5.5.

Метод секущихЗададим начальные значения x 0 и x1. Последующие значенияx n вычисляем по формулеx n 1  x n  r n  F ( x n ),где r n x n  x n 1F ( x n )  F ( x n 1 )n = 1, 2, …,.83Метод секущих является разностным аналогом методаНьютона. Он применяется в тех случаях, когда вычисление производной Fx (x) является затруднительным.Геометрическая интерпретация метода секущих состоит вследующем. Через две точки( x n 1 , F ( x n 1 ))и ( x n , F ( x n ))проводится прямая.

Абсциссаточки пересечения полученнойтаким образом прямой с осью хРис. 6и является новым приближением x n 1 к решению нелинейного уравнения (см. рис. 6).5.6. Мера погрешностиУсловием окончания итерационного процесса является выполнение одного из двух условий (выбор условия определяется соответствующим пунктом меню):|| x n  x n 1 ||  или|| F ( x n ) ||  .Значение  будем называть мерой погрешности.Следует заметить, что выполнение условия сходимости негарантирует, что последнее приближение x n находится достаточно близко от корня.В настоящей работе сходимость итерационного процессафиксируется следующими способами: сходимость по аргументуи сходимость по функции.5.7.

Сходимость по аргументуСчитается, что итерационный процесс сошелся, если выполнено условие|| x n  x n 1 ||  где  — мера погрешности.845.8. Сходимость по функцииСчитается, что итерационный процесс сошелся, если выполнено условие|| F ( x n ) || .5.9. Контрольные вопросы1.Требуется найти оба корня уравнения x  ln ( x  2).1.1.

Покажите, что для отыскания положительного корня можновоспользоватьсяитерационнымпроцессомx n 1  ln ( x n  2), где x 0 0 —произвольно.1.2. Можно ли указать x 0 , не совпадающее с отрицательнымкорнем заданного уравнения, таким образом, чтобы итерационный процесс x n 1  ln ( x n  2) сходился к отрицательному корню?1.3. Предложите способ вычисления отрицательного корня.2.

Выпишите формулы подходящего способа последовательных приближений для нахождения положительного корня нелинейного уравнения:x  x 3  0,1  0.Оцените необходимое число итераций для достижения точности   10 8 и сравните с тем числом, которое Вы получилипри расчетах на ЭВМ.3. Пусть уравнение f ( x)  g ( x)  0, где f (x ) и g (x) — заданные функции, решается методом Ньютона. Покажите, чтоприближение x n 1 имеет геометрический смысл абсциссы точки пересечения касательных к графикам y  f (x) и y  g (x),проведенным при x  x n .4.Пронумеруем корни x(n ), где n  0, 1, 2,  уравненияe  x  cos x в порядке возрастания.

Покажите, что при решенииуравнения e  x  cos x  0 методом Ньютона, итерации сходятся85к корню x(n ), если за x 0 ( n ) принять число x 0 ( n)  n/2.5.10. Порядок выполнения работы1. Решите уравнение x  tg x методом Ньютона. Как изменитсяхарактер сходимости с увеличением номера корня?2. Покажите, что для решения методом Ньютона следующихуравнений за x 0 можно принять любое положительное число:11) e  x  ;x2) e  x  x  2  0.Решите предложенные уравнения численно.3.

Отделите корни следующих уравнений, а затем уточните одиниз них с помощью итерационного процесса:1) arct g ( x  1)  2 x  0;3) 2 tg x x2 1  0;2) ln x  ( x  1) 3  0;4)x 1 1x.4. Уравнениеt  x3  x2 1  0зависит от времени t. Предложите итерационный алгоритм отыскания положения этих корней в зависимости от времени t завремя от t = 0 до t = 1.Выясните, при каком значении t эволюция отрицательногокорня заканчивается его исчезновением.5. Решите каждое уравнение различными методами с точностьюдо 10 6 и сравните их по эффективности. Объясните полученный результат.1) x ln x  1;2) cos 5 x  x 2 ;3) ln | x |  ( x  1)3  0;4) tg x  th x;865) 3 arctg1x12sh x  0 при x > 0.6. Методом Ньютона найдите корень уравнения x 7  0,5 с точностью до 10 6.

Рассмотрите отдельно критерии сходимости пофункции и по аргументу. Сравните результат и число итераций,требуемое для сходимости.5.11. Библиографическая справкаИтерационным методам решения нелинейных уравнений и систем посвящена обширная литература. Для выполнения работывполне достаточно ознакомиться с основными идеями и теоремами по книгам [1–3]. Более полные сведения о методе можнополучить из [8–10, 22], см.

также [23] и библиографию в ней.С итерационными методами решения нелинейных системтесно связаны различные дискретные отображения. О них лучше прочитать в [24, 25], а на более серьезном уровне в [26].87Л АБОР АТ ОРН АЯ РАБОТ А 6ПЕРЕОПРЕДЕЛЕННЫЕ СИСТЕМЫЛИНЕЙНЫХ УРАВНЕНИЙ.МЕТОД НАИМЕНЬШИХ КВАДРАТОВ6.1.

ВведениеРабота позволяет исследовать и продемонстрировать особенности нахождения обобщенного решения переопределенных систем линейных уравнений. Рассматриваются переопределенныесистемы линейных уравнений, возникающие, например, при обработке результатов физических экспериментов. Исследуетсявлияние выбора базиса (степенные и тригонометрические многочлены, многочлены Лежандра), степени многочлена на свойства вычислительного алгоритма и обусловленность возникающей задачи.6.2. Переопределенная системалинейных алгебраических уравненийКаноническая запись переопределенной системы линейных алгебраических уравнений имеет следующий вид:a11b1    a1s b s  f1 ,.....................................n > s.(6.1)a n1b1    a ns bs  f n ,Введем пространства R s и R n состоящие из элементоввида b  (b1 ,  , bs ) т , f  ( f1 ,  , f n ) т и имеющие размерности s и n > s соответственно. Обозначим через А прямоугольнуюматрицу системы (6.1):A88a11a1sa21a2s.an1ans(6.2)Тогда систему (6.1) можно записать в видеbRs,Ab  f ,f  Rn(6.3)Введем в R n «основное» скалярное произведение, положив(f , g ) ( n ) n(6.4)fk gk .k 1Скалярное произведение в R n можно ввести множеством других способов.

Характеристики

Список файлов книги