Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (pdf) (1113729), страница 9
Текст из файла (страница 9)
Для данного ε можно указать такое δ :0 < δ ≤ min( c − a , b − c ) , что для всех x ∈ [ c − δ , c + δ ] выполняется неравенствоϕ ′( x ) ≤m2.(34)f ( x) − f (c) = f ( x) ≤ ε =2MУчитывая это, получим окончательную оценку производной1ϕ′( x ) ≤ , c − δ ≤ x ≤ c + δ .(35)2В соответствии с результатами предыдущего параграфа, неравенство (35) означает,что уравнение (31) можно решать методом итераций: при любом выборе нулевогоприближения на отрезке [ c − δ , c + δ ] существует бесконечная последовательность(20), сходящаяся к корню x = c . Нам остается только заметить, что итерационнойпоследовательностью для уравнения (31) является последовательность (29) методакасательных.Требование близости нулевого приближения к искомому корню x = c являетсясущественным для метода касательных. На рис. 3 изображен график той же функцииf ( x) , что и на рис.
2, однако x0 выбрано дальше от корня x = c , чем в первом случае.В результате после первого шага получается точка x1 , которая не принадлежит- 40 исходному отрезку [ a, b ] и процесс построения рекуррентной последовательностиобрывается. Таким образом, для правильного выбора нулевого приближения нужноеще до начала расчетов знать область локализации искомого корня x = c . В случаенеобходимости ее можно уточнить с помощью нескольких шагов по методу вилки.Затруднения, связанные с предварительным исследованием уравнения, вполнеокупаются высокой скоростью сходимости метода касательных.Задача 3.Найти приближенное значение корня уравнения (16) методом касательных.Рекуррентная формула метода касательных принимает в данном случае видx − cos xnxn+1 = xn − n.(36)1 + sin xnВыберем, как и для метода итераций, в качестве нулевого приближения x0 = 0.5 иподсчитаем следующие приближения.
Результаты вычислений приведены в таблице 3.Мы видим, что, начиная с номера n = 1 , последовательность убывает, приближаясь ккорню x = c сверху. После четвертого шага процесс «останавливается»: пятаяитерация дает тот же результат. Причина этого явления заключается в следующем.Расчеты ведутся с 12 десятичными знаками. Когда погрешность оказывается меньше10−12 , становится невозможно уловить разницу между xn и xn+1 , лежащую запределами ошибки округления.Таблица 3.xnn0 0,5000000000001 0,7552224171062 0,7391416661503 0,7390851339214 0,7390851332155 0,739085133215Приведенный пример показывает очень высокую скорость сходимости методаНьютона.
После двух шагов мы достигли точности 10−4 . Это лучше результатов,которые мы имели в методе вилки на девятом шаге, в методе итераций – надевятнадцатом. После четырех шагов погрешность в определении корня составила10−12 .Задача 4.Рассмотреть вычисление a как задачу решения уравненияx2 − a = 0(37)в области x > 0 . Написать для вычисления корня уравнения (37) x = a итерационнуюпоследовательность по методу касательных.
Вычислить с ее помощью 2 .Рекуррентная формула метода касательных (29) для уравнения (37) принимаетвид- 41 xn 2 − a 1 ⎛a⎞(38)= ⎜ xn + ⎟ .xn +1 = xn −2 xn2⎝xn ⎠Она определяет монотонно убывающую последовательность, сходящуюся к aсверху.Перейдем ко второй части задания. Напомним, что 2 ≈ 1.414214 . Выбираяx0 = 2 , сделаем несколько итераций по формуле (38):x0 = 2,x1 = 1.5,1⎛ 3 4⎞x2 = ⎜ + ⎟ = 1.416666,2⎝ 2 3⎠1 ⎛ 17 24 ⎞x3 = ⎜ + ⎟ = 1.414216.2 ⎝ 12 17 ⎠Третья итерация определяет2 с погрешностью ∆ = 2 − x3 = -0.000002 .Расчет поформуле (38) много проще вычисленияaпоследовательного определения десятичных знаков.пошкольномуалгоритму§4. Заключительные замечанияМы познакомились с тремя методами численного решения уравнений, наряду сними существуют еще несколько методов, на которых мы не останавливались.Ситуация, когда одну и ту же математическую задачу можно решать с помощьюразных методов, является довольно типичной.
В таких случаях естественно возникаетнеобходимость сравнения их между собой.При оценке эффективности численных методов существенное значение имеютразличные свойства:1. Универсальность.2. Простота организации вычислительного процесса и контроля точности.3. Скорость сходимости.Посмотрим с этой точки зрения на разобранные методы решения уравнений.1. Наиболее универсальным является метод вилки: он требует только непрерывностифункции f ( x) .
Два других метода накладывают более жесткие ограничения. Вомногих случаях это преимущество метода вилки может иметь существенное значение.2. С точки зрения организации вычислительного процесса все три метода оченьпросты. Однако и здесь метод вилки обладает определенными преимуществами.Вычисления можно начинать с любого отрезка ⎡⎣ a, b ⎤⎦ , на концах которого функцияf ( x) принимает значения разных знаков. Процесс будет сходиться к корнюуравнения, причем на каждом шаге он дает двухстороннюю оценку, по которой легкоконтролировать достигнутую точность. Сходимость же метода итераций икасательных зависит от того, насколько удачно выбрано нулевое приближение.- 42 3.
Наибольшей скоростью сходимости обладает метод касательных. В случае, когдаподсчет значений функции f ( x) сложен и требует существенных затрат машинноговремени, это преимущество становится определяющим.Итак, мы видим, что ответ на вопрос о наилучшем численном методе решенияуравнений не однозначен. Он существенно зависит от того, какую дополнительнуюинформацию о функции f ( x) мы имеем и, в соответствии с этим, каким свойствамметода придаем наибольшее значение.- 42 -Глава 3. ПРИБЛИЖЕНИЕ ФУНКЦИЙ.Пусть на отрезке [a, b] определена некоторая функция y = f ( x ), однако полнаяинформация о ней недоступна. Известны лишь ее значения в конечном числе точекx0 , x1 ,K xn , этого отрезка, которые мы будем считать занумерованными в порядкевозрастания:(1)a ≤ x0 < x1 < K < xi < xi +1 < K xn ≤ b .Требуется по известным значениям(2)yi = f ( xi ) , i = 0,1,K , n«восстановить», хотя бы приближенно, исходную функцию y = f ( x ), то естьпостроить на отрезке [a , b] функцию F ( x ) , достаточно близкую к f ( x ) .
ФункциюF (x) принято называть интерполирующей функцией, точки x = x0 , x = x1 ,K x = xn узлами интерполяции.Подобные задачи часто возникают на практике, например, при обработкеэкспериментальных данных, когда значения переменной y , зависящей от x ,измеряется в конечном числе точек xi : yi = f ( xi ) , ( i = 0,1,K , n ) или при работе стабличными функциями, если требуется вычислить y = f ( x ), при значенияхаргумента , не совпадающего ни с одним из табличных xi .Поставленный выше в общей форме вопрос о приближении функций являетсядостаточно сложным. Существует не один подход к его решению. Мы ограничимсяизложением трех наиболее распространенных методов.§1. Интерполирование.1.1.
Классическая постановка задачи интерполирования.Выберем некоторую систему функций ϕ 0 ( x ), ϕ1 ( x ),Kϕ n ( x ) , заданных на отрезке[ a, b] , и будем строить F ( x ) как их линейную комбинацию:nF ( x ) = ∑ ciϕ i ( x ) ,i =0(3)где числовые коэффициенты ci (i = 0,1,K n ) подлежат определению, согласноусловиям:(4)F ( x j ) = f ( x j ) , j = 0,1,K , n .Равенства (4) представляют собой систему линейных алгебраических уравненийотносительно коэффициентов ci :n∑c ϕ (x ) = f (x ) ,i =0или в развернутом виде:iijjj = 0,1,K , n- 43 -⎧c0ϕ 0 ( x0 ) + c1ϕ1 ( x0 ) + K + cnϕ n ( x0 ) = f ( x0 )⎪c ϕ ( x ) + c ϕ ( x ) + K + c ϕ ( x ) = f ( x )⎪ 0 0 11 11n n11.(5)⎨M⎪⎪⎩c0ϕ 0 ( xn ) + c1ϕ1 ( xn ) + K + cnϕ n ( xn ) = f ( xn )Для того, чтобы коэффициенты ci (i = 0,1,K n ) можно было определить и притомединственным образом, необходимо и достаточно, чтобы определитель полученнойсистемы линейных уравнений был отличен от нуля:ϕ 0 ( x0 ) ϕ1 ( x0 ) K ϕ n ( x0 )ϕ 0 ( x1 ) ϕ1 ( x1 ) K ϕ n ( x1 )∆=≠ 0.(6)MMMMϕ 0 ( xn ) ϕ 1 ( xn ) K ϕ n ( x n )Определение.Система функций ϕ i ( x ) ( i = 0,1,K n ) , удовлетворяющая при фиксированныхзначениях x j ( j = 0,1,Kn ) условию (6), называется Чебышевской.Очевидно, что для однозначной разрешимости задачи интерполирования вклассической постановке необходимо и достаточно, чтобы система функцийϕ i ( x ) (i = 0,1,K n ) была Чебышевской.
Только такие системы функций мы и будемиспользовать в этой главе. Необходимым условием принадлежности системы функцийϕ i ( x ) (i = 0,1,K n ) к Чебышевской является их линейная независимость. Однако этоусловие не является достаточным. Например, для системы из двух линейнонезависимых функций ϕ 0 ( x ) = sin x, ϕ1 ( x ) = cos x , с узлами интерполяцииx0 = 0, x1 = π , определительsin x0 cos x0 0 1∆===0sin x1 cos x1 0 −1и данная система функций при выбранных значениях x0 и x1 не являетсяЧебышевской.1.2. Интерполирование полиномами.При построении интерполирующей функции F ( x ) в виде (3) функции ϕ i ( x ) ,естественно, выбираются такими, чтобы их вычисление было простым.
В частности,широкое распространение получило интерполирование с помощью степенныхфункций:ϕ 0 ( x ) = 1; ϕ1 ( x ) = x; ϕ 2 ( x ) = x 2 , K ϕ n ( x ) = x n .В этом случае интерполирующая функция представляет собой полином степени n :nF ( x ) = Pn ( x ) = ∑ ci x ii =0с неизвестными коэффициентами ci ( i = 0,1,K n) .(7)- 44 Согласно рассмотренной выше общей схеме построения интерполирующейфункции, следует потребовать, чтобы коэффициенты ci с учетом (7) удовлетворялисистеме линейных уравнений:n∑c xi =0iij= f ( x j ) , j = 0,1,K , n .(8)Определителем этой системы является определитель Ван-дер- Монда:1 x0 x02 K x0n1 x1 x12 K x1n∆== ∏ ( xi − x j ) .M MM MMi> j1 xn xn2 K xnnВ нашем случае этот определитель отличен от нуля, поскольку, согласно (1), все узлыинтерполирования различны между собой.
Итак, интерполирование с помощьюполиномов при сделанных в начале главы предположениях всегда осуществимо ипритом единственным образом.Задача 1.Построить линейный полиномP1 ( x ) = c0 + c1 xпо заданным узлам интерполяции x0 < x1 и соответствующим им значениям функцииy0 = f ( x0 ) и y1 = f ( x1 ) .Линейная система уравнений для определения c0 и c1 в данном случае имеет вид:c0 + c1 x0 = f ( x0 ) ,c0 + c1 x1 = f ( x1 ) .Определитель этой системы равен ∆ = x1 − x0 ≠ 0 . Решив систему, получим:x f ( x0 ) − x0 f ( x1 )f ( x1 ) − f ( x0 )c0 = 1; c1 =.x1 − x0x1 − x0Следовательно,x f ( x0 ) − x0 f ( x1 ) f ( x1 ) − f ( x0 )P1 ( x ) = 1+x.(9)x1 − x0x1 − x0Перепишем этот полином в несколько другой форме, выделяя f ( x0 ) и f ( x1 ) вкачестве множителейx − x0x − x1P1 ( x ) = f ( x0 )+ f ( x1 ).(10)x0 − x 1x1 − x0Геометрический образ интерполирующей функции P1 ( x ) - прямая, проходящая наплоскости ( x, y ) через точки с координатами ( x0 , y0 ) и ( x1 , y1 ) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
