Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 19
Текст из файла (страница 19)
Пусть функция ~ непрерывна на отрезке [а, о] и принимает на е|о концах значения разных знаков, т. е. ~(а).~(о) < О. То~да отрезок [а, о] содержит по крайней мере один корень уравнения Х(х) = О. К сожалению, корень четной кратности не удается локализовать на основании перемены знака с помощью даже очень подробной таблицы. Дело в том, что в малой окрестности такого корня (например, корня х2 на рис. 4,1) функция 1".имеет постоянный знак. Важно подчеркнуть, что далеко не всегда для успешного отыскания корня х уравнения (4.1) необходимо полное решение задачи локализации. Часто вместо отрезка локализации достаточно найти хорошее начальное приближение х~ о> к корню х. Пример 4 2.
Локализуем корни уравнения 4(1 — х2) — е = О. (4.4) Для этого преобразуем уравнение к виду 1 — х2 = 0.25ех и построим графики функций у = 1 — х2 и у = 0.25ех (рис. 4,2). Абсциссы точек пересечения этих графиков являются корнями данного уравнения. Из рис. 4.2 видно, . что уравнение имеет два корня х1 и х2, расположенные на отрезках [ — 1, 0] и [О, 1]. ~ бедимся, что функция 1(х) = 4(1 — х~) — ех принимает на концах указанных отрезков значения разных знаков.
рис 4 8 Действительно, 1 ( — 1) = -е 1 < О, У(0) = 3 > О, Х(1) = -е < О. Следовательно, в силу теоремы 4.1 на каждом из отрезков [ — 1, О] и [О, 1] находится по крайней мере один корень. Пример 4 3. Локализуем корни уравнения хз — 1.1хт — 2.2х+ 1.8 = О. Для этого составим таблицу значений функции 1(х) = хз — 1.1ха — 2.2х + 1.8 на отрезке [ — 2, 2] с шагом 0.4. Таблица 4.1 — 2.0 -1.6 -1.2 -0.8 -0.4 О.О -6.200 -1.592 1.128 2.344 2.440 1.800 Продолжение табл. 4.1 0.4 0.8 1.2 1.6 2.0 0,808 -0.152 -0,696 -0,440 1.000 84 Из табл.
4.1 видно, что функция Р" меняет знак на концах отрезков [-1.6, -1.2], [0.4, 0.81, [1.6, 2.01. Теорема 4.1 дает основание утверждать, что камсдый из этих отрезков содержит по крайней мере один корень. Учитывая, что в силу основной теоремы алгебры многочлен третьей степени не может иметь более трех корней, заключаем, что полученные три отрезка содержат ровно по одному корню. Таким образом, корни локализованы.
Итерационное уточнение корней. Наэтом этапе для вычисления каждого из корней с точностью в > О используют тот или иной итерационный метод, позволяющий построить последова- ) х<"' — х~ ~ сод". (4.5) Как нетрудно видеть, из оценки (4.5) действительно вытекает сходимость метода. Пусть одношаговый итерационный метод обладает следующим свойством: существует о-окрестность корня х такая, что если прибли- жение х» "» принадлежит этой окрестности, то справедлива оценка (4.6) где С > О и р ~ 1 — постоянные. В этом случае число р называют порядком сходимости метода.
Если р = 1 и С < 1, то говорят, что метод обладает линейной скоростью сходимости в указанной а-окрестности корня. Если р > 1, то принято говорить о сверхлинейной скорости сходимости. При р = 2 скорость сходимости называют квадра- 85 тельность х<о', х<Ы, ..., х<"', ... приближений к корню х.
Общее представление об итерационных методах и основные определения были даны в 8 3.3. Введем дополнительно некоторые определения. Итерационный метод называют одногааговым, если для вычисления очередного приближения х'"+" используется только одно предыдущее приближение х' "' и й-гааговым, если для вычисления х' ""' используются й предыдущих приближений х<" Ь г', х'" »< 2», ..., х<"'. Заметим, что для построения итерационной последовательности одношаговым методом требуется задание только одного начального приближения х< о», в то время как при использовании Х-шагового метода — к начальных приближений х<ог, х'г', ..., х<»» ы.
Скорость сходимости — одна из важнейших характеристик итерационных методов. Говорят, что иетод сходится со скоростью геометрической прогрессии, знаменатель которой д < 1, если для всех и справедлива следующая оценка: тичной, а при р = 3 — кубической. При наличии оценки (4.6) у й-шагового метода (при Й ) 1) число р также будем называть порядком сходимости метода. Л е и и а 4.1.
Пусть одногиаговый итерационный иетод обладает линейной скоростью сходимосгпи в некотпорой <г-окрестности корня х. Тогда при любом выборе начально~о приближения х' с) из окрестности корня х итерационная последовательность х< т не выходит за пределы этой окрестности, метод сходится со скоростью геометрической прогрессии со знаменателелг д = С и и иеегп месгпо следуюигая оценка погреигностиг !х:") — х! ( д"!х<()) — х!, и э О. (4.7) () Заметим, что принадлежность х<") окрестности (х — (т, х + (г) является следствием неравенства (4.7).
В самом деле, так как д ( 1, то !х(п) — х! ~~ !х(о) — х! < о. Сходимость х<") к х также вытекает из (4.7). Справедливость неравенства (4.7) установим методом индукции. При и = О оно переходит в очевидное: ! х< с) — х! < ! х(о) — х!. Пусть неравенство (4.7) выполнено при и = т — 1. Тогда !х(щ) — х! ~ Ч!х( 1) — х! 4 дп!х<0) х! т. е.
неравенство выполнено и при и = т. 9 Л е и м а 4.2 Пусть М вЂ” гиаговый итерационный метод в некоторой приближения х<о) из 5-окрестности корня х итерационная последовательность х'"' не выходит за пределы этой окрестности, метод сходится и справедлива оценка ! х' "' — х! ч С< дР, п З О, (4.8) где д = С~~~ !х<()) — х!, С) = С~~ (Р <'. и Заметим, что принадлежность х(") окрестности (х — б, х + б) является следствием неравенства (4.8). В самом деле, так как д < 1 и 1 ~ р", то из (4.8) вытекает, что !х'") — х! < С)о = !х<в) — х! ( 6. Сходимость х< ") к х также следует из (4.8).
86 в-окрестности корня х имеет р-й порядок сходимости. Выберем б > О,( так, чтобы выполнялись неравенства б ~( в и Сбр ' < 1, где С вЂ” постоянная из неравенства (4.6). Тогда при любом выборе начального Справедливость неравенства (4.8) установим методом индукции. При а = 0 оно переходит в очевидное: ~ х< 0> — х~ ( ~ х< э> — х~ . Пусть неравенство (4.8) выполнено при в = т — 1. Докажем, что оно верно и при и = и<. Используя условие (4.6), получаем С помощью доказанных лемм исследование сходимости итерационных методов сводится только к получению оценки (4.6).
з 4.2. Обусловленность задачи вычисления корня Пусть с — корень уравнения (4.1), подлежащий определению. Бу- дем считать, что входными данными для задачи вычисления корня с являются значения < (х) функции ~ в малой окрестности корня. Так как значения ~(с) будут вычисляться на ЭВМ по некоторой программе, то в действительности задаваемые значения являются приближенными и их следует обозначать через ~~(т). Ошибки в ~*(х) могут быть связаны не только с неизбежными ошибками округления, но и с использованием для вычисления значений функции < приближенных методов. К сожалению, нельзя ожидать, что в окрестности корня относительная погрешность 0(~*) окажется малой.
Достаточно обратиться к примерам 2.11 и 3.11, чтобы установить, что для чрезвычайно простых функций у = 1 — с и у = з<п х в окрестности корней х = 1 и с = х значения этих функций не могут быть найдены с малой относительной погрешностью. Реально рассчитывать можно лишь на то, что малой окажется абсолютная погрешность вычисления значений функции. Будем предполагать, что в достаточно малой окрестности корня выполняется неравенство ~~(х) — 1*(с) ~ ( Ь, где Ь = Ь(~*) — граница абсолютной погрешности. Сама погрешность корня ведет себя крайне нерегулярно и в первом приближении может восприниматься пользователем как некоторая случайная величина. На рис.
4.3, а представлена идеальная ситуация, отвечающая исходной математической постановке задачи, а на рис. 4.3, 0 — реальная ситуация, соответствующая вычислениям значений функции У на ЭВМ. Если функция ~ непрерывна, то найдется такая малая окрестность (х — е, х + е) корня х, имеющая радиус е > О, в которой выполняется неравенство !У(х)~ < Ь. (4.9) Для х Е (х — е, х + е) знак вычисленного значения ~'(х), вообще говоря, не обязан совпадать со знаком ~(х) и, следовательно, становится невозможным определить, какое именно значение х из интервала (х — е, х + е) обращает функцию ~в нуль (рис. 4.3, б).
Будем называть этот интервал интервалом неопределенности корня х. Найдем оценку величины е. Пусть корень х — простой. Для близких к х значений х справедливо приближенное равенство х — <х<х+ 1Х' ( х)! Т( )1 (4.10) ~(х) ~ ~(х) + ~ (х)(х— Поэтому неравенство (4.9) чаем Следовательно, еми Ь(~*). х) = ~ (х)(х — х). примет вид ~~'(х)(х — х) ~ < Ь, откуда полу- 1 Здесь и = — число, которое в рассматриваемой задаче играет 1Х'(х)! роль абсолютного числа обусловленности. Действительно, если х'— корень уравнения ~*(х) = О, то )~(х') ~ с Ь и тогда выполнено нера- венство 1 х — х*! ~ Ь(х *) 4 е м уайет'). (4.11) Заметим, что радиус интервала неопределенности прямо пропорционален погрешности Ь вычисления значения ~ Кроме того, е воз- Если же 1"(х) = О (т.
е. корень х — кратный), то формула (4.1О) уже не верна. Пусть кратность корня равна тп. Тогда в силу формулы Тейлора' справедливо приближенное равенство У"(х) УМ в) (х) у (х) - 1". (х) + у'(х)(х — х) + —, (х — х)т + ... +, (х — х)а, ~ Брук Тейлор (1685 — 1731) — английский математик и философ.
Широко известная формула разложения функции в степенной ряд была получена им в 1712 г. 89 растает (обусловленность задачи ухудшается) с уменьшением ~~'(х)~, т. е. с уменьшением модуля тангенса угла наклона, под которым гра- фик функции пересекает ось Ох (рис. 4.4, а, 6). в правой части которого все слагаемые, кроме последнего, равны нулю.
Следовательно, неравенство (4.9) имеет вид Решая его, получаем аналогично (4.10) оценку радиуса интервала неопределенности: >/ см ' Ь/". /> в> (~) Эта оценка означает, что для корня кратности т радиус интервала 1/ неопределенности пропорционален Ь ", что свидетельствует о плохой обусловленности задачи вычисления кратных корней. С этой неприятностью мы уже сталкивались при рассмотрении примера 3.9. Отметим, что к не может быть меньше величины ~х~~„— погреш— ности представления корня х в ЭВМ.
В реальной ситуации оценить величину и даже порядок радиуса интервала неопределенности довольно сложно. Однако знать о его существовании нужно по крайней мере по двум причинам. Во-первых, не имеет смысла ставить задачу о вычислении корня х с точностью е < в. В условиях неопределенности, вызванных приближенным зада- нием функции, любое значение х* Е (г — я, с + я) может быть с одной и той же степенью достоверности принято за решение уравнения. Вовторых, нельзя требовать от алгоритмов отыскания корня получения достоверных результатов после того, как очередное приближение попало в интервал неопределенности или оказалось очень близко от него; в этой ситуации вычисления следует прекратить и считать, что получен максимум действительно возможного.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
