Дьяченко В.Ф. Основные понятия вычислительной математики (Дьяченко В.Ф. Основные понятия вычислительной математики.djvu), страница 2

Разумеется, это можно сделать не единственным образом. Так, уравнение (1) можно представить, наряду с (2), в виде клк а х = 2х —— х И Нетрудно установить, что ни та, ни другая формула не годится для итераций. Первая дает х> = а/хю х, = хю х, = а/х„..., а вторая порождает последовательность х„, стремящуюся к бесконечности. Таким образом, далеко не всякая запись уравнения (8) в виде (10) приводит к цели. Выясним, какие свойства >р (х) влияют на сходимость процесса. Поскольку последняя означает, что х„— Х->.

0 при п -э оо, то нужно, чтобы ! х„— Х ! убывало с ростом и. Пусть для любого л справедливо неравенство (х„— Х!(9(х„> — Х!, 6(1. (11) Тогда, очевидно, ! х„— Х ! убывает как геометрическая прогрессия со знаменателем 9, т. е. сходимость имеет место. Подставим в левую часть (11) вместо х„и Х соответственно >р (х„) и >р (Х). Получим !>Р(х >) — <Р(Х)(<9!х„,— Х!, 6(1. (12) Так как корень Х неизвестен, то последнее условие непосредственно проверить нельая и приходится несколько усилить его.

Выше мы предполагали, что корень локализован внутри некоторого интервала. Если для любой пары точек х', х" из этого интервала выполнено условие ! >р (х') — >р (х') ! ( 6 ! х — х' (, 6 (1, (13) то заведомо выполнено и (12). Отображение х = ~р (х), удовлетворяющее (13), называют с>хал>мм отображением (оно сжимает отрезки х" — х'). Очевидно, условие (13) есть достаточное условие сходимости итерационного процесса (9). Для конкретной оценки величины 6, определяющей скорость сходимости, проще всего пользоваться очевидной формулой 6 = шах(>р'(х) (, (1 4) где шах берется по интервалу локализации корня.

Если отображение х = у (х) — сжатое, то этот интервал с ростом п будет уменьшаться,и оценку скорости сходимости можно уточнять. Итак, любая запись уравнения (8) в виде (10), удовлетворяющая условию (13), дает итерационный процесс, сходящийся к корню. Качество того или иного выбора ~р (х), очевидно, следует оценивать по скорости сходимости. Лучшим в этом смысле естественно считать тот, для которого величина 8 будет наименьшей.

Пустыр (х) таково, что уравнения 7(х) =О и <р (х) х — О имеют общий корень Х. Тогда, если этот корень не кратный, г"(Х) + О, з некоторой окрестности его, где нет других нулей функции 7 (х), отношение — = г(х) 'р (*) Р (*) есть ограниченная функция. Каждой функции ~р (х) соот- ветствует г (х) и, обратно, каждая ограниченная г (х) по- рождает <р (х) = х + г (х) г (х).

(15) Нас интересуют р (х) с минимальным) ~р' (х) ( (в силу (14)). Продифференцируем выражение (15), ~р' = 1 + г (х) г' (х) + г' (х) ~ (х). В районе корня величина / (х) мала, поэтому пренебрежем последним слагаемым и приравняем нулю оставшееся выражение. Это даст 1 г(х) = — —, т. е., в соответствии с (15), функцию ~р(х) = х — —, 1(*) )'(х) ' (16) порождающую итерационный процесс, известный как метод Ньютона, 1(х т) (1 7) ея-г) Скорость сходимости этого процесса очень высока, так как ~р'( ) = ~, ( ),1(х) по мере приближения к корню. Формулу (17) можно получить и другим путем (рис. 2). А именно, имея некоторое приближение для корня х„„ при вычислении следующего приближения х„будем (з вместо уравнения ~ (х) = О рассматривать линейное уравнение г (л„,) + >' (х„,<).

(л — л„>) = О, учитывающее лишь два первых члена разложения функции~ (х) в ряд Тейлора около точки х„,. Решая последнее уравнение относительно х, получаем формулу (17). Преимущества мето- У да Ньютона сказыва- ются только в окрест! ности корня, где <р' мало. Поэтому в конкретных расчетах следует сначала локализовать корень каким-нибудь у-1Ф более простыми грубым у-фч ~',<з-д„„> способом, а затем для быстрого достижения высокой точности использовать метод Ньютона.

Точность вычислений (количество удерживаемых десятичных знаков) рационально сделать переменной, увеличивая ее по мере приближения к корню. При этом, поскольку переход от х„, к з„ является одновременно проверкой уравнения л = <р (х), эквивалентного ~ (х) = О, то достигнутую точность можно оценивать по числу не меняющихся при этом переходе знаков. Изложенный итерационный метод нахождения корня, использующий сжатые отображения, можно без принципиальных изменений распространить на многие более сложные задачи.

Пусть требуется решить систему М уравнений с М неиавестными $< 4> (хн>, х<з>,..., з<м>) = О, и = 1, 2,..., М. (18) Обозначим вектор с компонентами Р», 1тз>, ..., ~<м> через ~, соответственно л<», х<'>, ..., х<м> через х и запишем систему (18) в виде векторного уравнения >(х) =О, (19) по форме совпадающего с (8). Все сказанное относительно уравнения (8) переносится на систему (19), нужно только, учитывая векторный характер величин, придать новый смысл употребляемым обозначениям.

14 Для оценки величины скаляра испольауется его модуль, для вектора — его норма. Мы определим последнюю как максимум модуля компонент (20) Очевидно, равенство нормы вектора нулю овначает равенство нулю всех его компонент. Перепишем систему ($9) в виде х = <р(х), ~ф(х") — ф(х')~(6)1х" — х'~, 9((. (22) Оценим величину О. Рассмотрим функцию ф< > (х) на прямой, соединяющей точки х' и х". Получим функцию скалярного аргумента г ф(г) = ф<~> (х' + г(х — х')). (23) Точки х' и х" соответствуют эначенням а = 0 и а = $. Очевидно, «р< ) (х') — <р< ) (х') = ф($) — ф (0) = ф' (а), (24) причем 0 ( г ( т.

Дифференцируя (23) ко г, получим ф'(г) = „~~ <„> ((х<)о)' — (х<"))'). аф<") а=< Вместе с (24) это дает ! ф<~> (х') — ф<~> (х') ! ( 1 ар<"') ~ шах,'5~~ 1 — „) ! шах ~ (х<"> )' — (х<г))' 1. Испольауя определение кормы (20), получаем отсюда м <в ею ) <э>- <))~ *Х<~! <'-'<. т х )1 дхоо (25) где <р — вектор с компонентами ф<)), ф<е), ..., -ф<м). Как и прежде, формула (21) порождает итерационный процесс, условием сходимости которого является сжатость ото- бражения (2$), т.

е. Роль ~р' теперь, естественно, играет матрица производд~р~~~ ных — — производная вектор-функции по вектор- дав) ному аргументу. Если мы определим норму этой матрицы формулой д<р ом ю= *2,. ), (26) то для оценки величины 6 в условии (22), как следует из (25), можно воспользоваться равенством 9 = шах~ср'(х)~, х обобщающим (14) на векторный случай.

Далее, построение ~р (х) можно по-прежнему производить с помощью ($5) ~р (х) = х + г (х) ) (х), (28) где г (х) — произвольная матрица функций. При г (х) = †()' (х)) ~, (29) При значительном порядке системы М это может оказаться довольно трудоемким. Поэтому обычно данный метод используется лишь при наличии хорошего приближения для корней, когда одна-две итерации дают резкое повышение точности. Относительно решения систем линейных уравнений заметим следующее. Если нужно решить систему общего вида, то ничего лучше известного метода исключения не существует.

Однако, используя специфику конкретных систем, часто удается построить достаточно эффективные итерационные методы. где К) ' — матрица, обратная матрице производных р'=д)< ~!дхЖ, получим метод Ньютона. Он и здесь сохраняет свои преимущества, так как соответствующая ему матрица р' в точке корня будет нулевой. В этом легко убедиться, дифференцируя (28) и используя (29). При применении метода Ньютона теперь, вместо деления на функцию )', требуется обращение матрицы ~', т.

е. решение на каждой итерации системы линейных уравнений ~ (х„1) + ~' (х„1) (х — х„1) = О. Задачи 1. Построить итерационный процесс для извлечения корня степени р. 2. Определить скорость сходимости метода Ньютона з окрествости й-кратного карня. 3. Построить итерационный процесс решения уравнения ах+ Ь = О, где 0,1 с. а < 1, не использующий операции деления. 4. Дана система линейных уравнений Ах + Ь = 0 с матрицей А, все собственные значения которой действительны, раалвчны, положительны и заведомо заключены внутри некоторого известного интервала (а, б). Подобрать число г так, чтобы итерационный процесс х„х + г(Ах„+ Ь) сходился возможно быстрее.

$2. ФУНКЦИИ И ТАБЛИЦЫ Функция является фундаментальным математическим понятием и, естественно, присутствует в формулировках большинства задач. На языке численных методов функцию могут представлять, очевидно, только числовые после' довательности. Возможны различные способы такого представления, например, с помощью коэффициентов ряда по каким-либо функциям или значений параметров в формуле заданного вида.

Наиболее употребительным и универсальным является представление функции в виде таблицы ее значений. Так все «элементарные» функции з(п х, !и х, и т. д.— это таблицы. Рассмотрим функцию г" (х) и соответствующую ей таблицу — пару последовательностей х„, ~а (я = О, г, 2, ...). Качество этого соответствия будем оценивать по точности, с которой таблица х„, уа позволяет восстановить значение и" (х) в любой точке х. Очевидно, эта точность зависит от близости /т к г" (ха) и плотности расположения узлов таблицы х„. Роль первого фактора ясна — отклонение )» от р (х„) ставит предел точности воспроизведения, который, не исправляя таблицы, превзойти нельзя.