Бабенко - Основы численного анализа (947491), страница 110
Текст из файла (страница 110)
( ) ~ (') -'0 ,т„-б-.. (,) „,(„0((.ь-е). Отсюда и, стало быть, налицо квадратичная сходимость. 3 а д а ч а 10. Пусть б — вещественный корень кратности з. Положим 1п1 (ТО1(х)! = т„впр )~м ~~(х)! = М,ы. 1 л,О <лО Докажите, что 1хл-л --б~ < х, г в(в — 1) пм Здесь через (хы б) обозначен открытый интервал с крайними точками хь и р.
Если мы используем метод секущих, то. полагая в (21) гь г = ( + +ьь ы хь = ~ —, ьа и записывая с помощью формулы Тейлора гь г и гь, получим ОЫ ~) Нри в = 2 отсюда получаем чь- г чь ьь-г — ьь 'Зб, Реилснис нслинейннв дрленсний и систем уравнений 535 а переходя к обратным величинам, имеем 1 1 1 +— чьлл ба л бл Таким образом. мы вновь пришли к уравнению Фибоначчи.
Следователь- но. (Л вЂ”, 1)" ? л'5 — 1)" и поэтому ~'и.л 2 1 бл Л+ 1 1,62 (27) 7. Отделение комплексных корней. Рассмозрилс один из способов, с помощью которых можно в принципе попасть в сколь угодно малую окрестность некоторого корня многочлена (1). Этот способ внешне вьплядит вполне убедительно, но нри его численной реализации нужно принимать во внимание все то, что говорилось в п. 1 об обусловленности задачи отыскания корня многочлена. Пусть ?(я) ) О, ?: Р— К (Р С К"). Допустим, что ? 6 Сз(Р) и что зта функция имеет в области Р изолированные корни. Тогда, если двигаться вдоль траектории дифференциального уравнения е?т — = — ягас( 7, е?? (28) т.е. погрешность ~,' на каждом шаге уменьшается примерно в 1,62 раза.
Если сравнивать этот результат с форлсулой (26) при е = 2, то увидилц что две итерации метода секущих более выгодны, чем один шаг итерации метода Ньютона. Отметим. что мы не дали строгого вывода соотношений (25), (27), а привели лишь наводящие выкладки. Такой способ действительно довольно часто практикуется в численном анализе., и читателю нужно быть к нему готовым. Можно дать абсолютно строгое доказательство соотнолпений (25)., (27). В заключение остановимся на вопросе об удалении вычисленных корней. Если найдено приближенное значение -' корня ем то мы определиле функцию д(е) =. 7(с)?(е — -~л) и для нее будем отыскивать следующие корни.
Если применяются итерационные методы, основанные на использовании производных, то достаточно заметить, что д'(в)?'д(в) = ~'(аИ(в) — (- — ал), и мы вычислим д', если можем вычислить д, 7, ?'. Найдя приближенное значение св корня аз, будем находить корни функции ?л(е) — -- ?(в)?(е -- е')(в -- аз). Для д',?дл получим формулу, аналогичную приведенной выше. Такой процесс исчерпывания будем применять, пока пе найдем нужяое число корней, В каком порядке нужно исчерпывать корни, и как влияет процесс исчерпыванияу Эти вопросы мы оставим без ответа, а заметим, что имеются свидетельства в пользу того, что процесс исчерпывания нужно вести, начиная с корней, малых по модулю, и вести его в порядке возрастания модулей корней.
536 Глава 3, Творил изнвроций и лзвтоды решения ивиопзорьзх ввдач отправляясь от некоторой точки х,", мы придем в некоторую критическую точку функции /, которая может быть либо изолированным нулем, либо критической точкой х', для которой /(хз) > О, 8гад /~ =- О. В самом деле, вдоль интегральной кривой уравнения (28) д/ г дхт — =- ~8тад /, — ) —. — (8гад /, 8гад /) ( О, й ' й если х не является критической точкой /. Применим такой способ к отысканию нулей многочлена (1).
Положим /(г) = ~р(г), :и рассмотрим аналитический ландшафт мнозгочле,и на р(-), т.е. график функции р(г); над а-сферой. Функция / в силу принципа максимума для регулярных функций имеет точки минимума в нулях многочлена р и критические точки типа седла в нулях производной р'(-). Других локальных максимумов и минимумов эта функция не имеет.
Система (28) в данном случае примет вид дх д з ду д — = - —. ~р(в) — = - — М ) й, Вт ' й Озу Вычисляя отсюда дг/й —. дх/й — гду/вМ, получим более изящную форму предыдущей системы: дс — = — 2рз(г)р(в). й На интегральных кривых этого уравнения можно ввести другую параметризацию, положив дп = 2~р (а) ~ й. Тогда получим окончательно дифференциальное уравнение дв р(г) дп р'(г) Воспользуемся простейшим методом решения задачи Коши -- методом Эйлера. Если -е данные Коши, то — 1=О 1 йь р'( ь) откуда ь-зг вь — Ьь,, Й вЂ” --0,1,...
р( ь) (29) р'( ь) ' Мы получили формулу итераций, несколько более общую, чем формулу Ньютона. Применяя соответствующую тактику выбора шагов Ьзь всегда можно добиться того, чтобы через некоторое количество шагов мы попали в малуюю окрестность какого-то нуля многочлона р(-). Во всяком случае, если будем выбирать шаг 6ь не слизпком малым и так, чтобы выполнялось 'з 7. Мссиоди рсиасиил алгсбраи соской ароблсмм собстосиимк оиачсиий ос37 неравенство ~р(ил+1) < )р(вь)~ мы за конечное число шагов достигнем цели. Наш способ локализации корня аналогичен методам поиска минимума функций многих переменных с помощью наискорейшего градиентного спуска. В этих методах разрабатаны алгоритмы выбора шагов 6ь, и читатель может воспользоваться соответствующими рекомеядациями.
Однако все эти изощренные рекомендации не дают ответа на следующий вопрос: какова временная сложность оптимального алгоритма, обеспечивающего попадание в один из кругов К, введенных в п. 2, если мы начинаем двигаться из некоторой фиксированной точки во и если ограничим множество допустимых мпогочлеиов многочлспами р(в) вида рЯ=з" +а1ва +...— аа()а)<;3,1=1.,2,....п)? 8. О решении систем нелинейных уравнений скажем лиспь несколько общих слов. Итерационные методы реп|ения таких систем рассмотрены в гл.
2, где мы исследовали методы Ньютона и простых итераций и рассмотрели структуру инвариантных притягивающих множеств. Конечно, основным вопросом является вопрос о том, как попасть в надлежащую окрестность решения. Иногда приходится решать вопрос о том, имеет ли система нелинейных уравнений решение в заданной области Р. Для ответа на эти вопросы разработаны специальные алгоритмы. основанные на простых топологических фактах. Реализации этих алгоритмов довольно сложны., и при проведении вычислений мы сталкиваемся с целым рядом критических ситуаций, крайне затрудняющих вычисления. Подробности об этих алгоритмах читатель может найти в [150).
Но в действительности во многих случаях вопрос о решении нелинейных уравпония не такой острый. С нелинейными системами мы часто встрочаемся при решении краевых задач. Но тогда, как правило, мы располагаем хорошими начальными данными, поскольку больпюе внимание при конструировании алгоритма уделяется именно способам получения хоршпих начальных данных с использованием для этого специфики задачи. Как это делается, нужно рассматривать особо и отдельно в каждом конкретном случае. 8 7.
Методы решения алгебраической проблемы собственных значений 1. Введение. В и. 4 з 1 мы рассмотрели вопрос об обусшовленности проблемы собственных значений для матриц общего вида. Как известно., проблема собственных значений матрицы А размером и х и состоит в нахождении Л е С и вектора х, таких, ио (А — Л У)х, = О. Собственное значение Ло является корнем характеристического много- члена (2) р(Л) = с$ес(А — Л1), 538 Глава 8, Гвория иьварачий и мвтоды рвиьмшя нвкошорых задач который принято записывать в виде р<Л) —.... < — 1)а(Ли+ р,Ла-' + р,Л'-з —....).
Коэффициенты характеристического многочлена можно выразить через льиноры матрицы А, если разложить детерминант (2) по степеням переменной Л. Однако вычислительная работа при прямом проведении этой процедуры будет огромной. Поэтому появился ряд методов, позволяющих вычислить коэффициенты многочлена р1Л), не прибегая при атолл к вычислению миноров матрицы А. Это, прежде всего, методы Крылова, Данилевского, Леверье п др. Во всех этих методах вычисляются коэффициенты характеристического многочлеьга, затем решается уравнение (3) р(Л) = 0 и находятся собственные значения Ль, ..., Л„. При вычислении собственных векторов удается воспользоваться вспомогательными величинами, которые были вычислены в процессе определения р(Л), и тем сальыль упростить вычисления по сравнению с прямыль решением системы 11).
Однако все эти методы пригодны лишь для очень небольших порядков льатрицы А. Мьь уже отмечали, что представление миогочлена с помощью степешюго базиса 1, Л, ..., Л" это численно неустойчивая процедура. Коэффициенты многочлепа р(Л) при больших п часто будут экспоненпиально велики, и поэтому при определении их корней будет происходить огромное сокращение знаков, что скажется на точности, с которой мы их получаем. Кроме гого, при неблагоприятном расположении собственных значений Ль, ..., Л„в комплексной плоскости С сама задача решения уравнения (3) может оказаться плохо обусловленной, и это будет дополнительным обстоятельством, приводящим к потере точности.
Поэтому в практической дсятсльпости зти методы решения полной задачи па собственные значения вытеснены итерационными методами. Из всей группы этих точных методов (слово чточььых» на,члежало бы поставить в кавычки) мы опишем лишь один из методов интерполяционный ввиду его исключительной простоты, а с остальными методами читатель может познакомиться по мояографии )114), Как мы знаем, мпогочлен и-ьь степени определяется по его значениям в и+ 1 точках рь, ..., р„»ь.
Поэтому, если мы вычис ьим детерминант (2) пРи Л .—.. Рз (д' .—... 1, 2, ..., п + 1) то сможем восстановить Р(Л), пользУЯсь интерполяционной формулой Лагранжа: в ь р(Л) = ~ р~д,)1„п,<Л), где 1„»ь з(Л) фундаментальные многочлены интерполяции. Величины р(рь) можно вычислить, пользуясь методом Гаусса. сюгласно алгоритму., изложенному в п. 3 32. Если п невелико (и = 3+ 5), то можно игнорировать трудяость, связанную с величиной константы Лобега 67.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
