Вычислительная математика.

Литература

Демидович Б. П., Марон И. А. Вычислительная математика.

Данилина Л. И., Дубровская Н. С. Вычислительная математика.

Боглаев Ю. П. Вычислительная математика и программирование.

Волков Е. А. Численные методы.

Васильков Ю. В., Василькова. Компьютерные технологии вычислений, математическое моделирование.

Вычислительная математика – это раздел математики, изучающий круг вопросов, связанных с применением ЭВМ.

Математическая модель – описание в виде системы уравнений и количественных связей изучаемого явления или объекта.

Адекватность математической модели – способность правильно отражать свойства объекта.

Преимущество математической модели состоит в возможности предсказывать, прогнозировать свойства и характеристики объекта или явления.

Численный эксперимент – это расчет на модели.

Доверие к численному эксперименту базируется на надежности (адекватности) математической модели, что, в свою очередь, обеспечивает эффективный алгоритм решения задачи.

Для "чистого" математика решить задачу – значит доказать существование решения и указать процесс, сходящийся к решению.

Для "вычислителя" важно время получения решения, т. е. скорость сходимости процесса.

Например, для решения системы n линейных алгебраических уравнений с n неизвестными методом Крамера требуется n•n! простейших действий (сложение, вычитание, умножение, деление). При этом для 20 уравнений потребуется 5•10¹⁹ операций. Если операций больше, чем 10⁵-10¹⁰, то результат будет неверным из-за вычислительной погрешности.

Если же использовать метод Гаусса, то потребуется n³ операций, или, в нашем случае 8000.

Существует вычислительная погрешность, поэтому в большинстве случаев "вычислитель" отдает предпочтение алгоритмам последовательного приближения, а не точным алгоритмам.

Типичные задачи вычислительной математики:

1) Решение алгебраических и трансцендентных уравнений.

2) Решение систем линейных алгебраических уравнений.

3) Интерполирование и экстраполирование.

4) Численное интегрирование.

5) Численное дифференцирование.

6) Решение дифференциальных уравнение и их систем.

7) Оптимальные и обратные задачи.

8) Вычисление математических функций в ЭВМ.

9) Сортировка и упорядочивание массивов данных.

Тема 1: Приближенное решение алгебраических и трансцендентных уравнений.

1. Постановка задачи.

Дано уравнение с одним неизвестным f(x)=0 (1).

f(x) определена и непрерывна на промежутке (a; b). На этом промежутке также непрерывны первая и вторая производные этой функции.

Корнем или нулем функции (1) называется всякое значение ξ такое, что f(ξ)=0.

Изолированность корня – существование окрестности корня, в которой нет других корней.

Три этапа вычисления корней.

1. Определение области, в которой находятся все корни.

2. Отделение корней, т. е. указание возможно малого интервала (a_k, b_k), в котором содержится только один корень уравнения (1).

3. Уточнение приближенных корней, т. е. доведение их до заданной степени точности.

На первом этапе применяются исключительно математические методы. На втором – математические методы, графический метод и метод проб. На третьем применяются различные численные методы (проб, половинного деления, итераций, Ньютона, хорд и т. д.). Также на третьем этапе учитывается погрешность.

2. Общие критерии для отделения корней уравнения.

Теорема 1. Если непрерывная функция f(x) принимает значения разных знаков на концах отрезка [a, b], т. е. f(a)•f(b)<0, то внутри этого отрезка содержится, по крайней мере, один корень уравнения (1).

] f(x) C⁰(a, b) U f(a)•f(b)<0   ξ[a, b]:f(ξ)=0

Геометрическое толкование.

Очевидно, что если функция на концах отрезка принимает значения разных знаков, то она должна где-то менять знак, т. е. быть равной нулю.

Теорема 1 не обеспечивает единственность корня на промежутке.

Теорема 1'. Если для любого x из интервала (a, b) функция f(x) непрерывна и монотонна, а на концах интервала принимает значения разных знаков, то на рассматриваемом интервале находится один и только один корень уравнения (1).

В качестве признака монотонности удобно использовать критерий знакопостоянства производной.

]x(a, b) f'(x)>0  f'(x)<0  f(a)•f(b)<0   ξ(a, b):f(ξ)=0

Пример.

f(x)=x³-x-1=0

f'(x)=3x²-1

3x²-1=0

x=±

Получается три промежутка монотонности функции. Определив знак функции на этих промежутках, получим, что корень находится на промежутке ( ; ∞). Посчитав, например, f(2), получим, что на участке ( , 2) имее тся один корень.

2. Графическое отделение корней.

Если уравнение представлено в виде (1), то корень будет там, где график пересекается с осью абсцисс. Однако, уравнение (1) можно привести к виду φ₁(x)=φ₂(x) (2). Тогда корень будет в месте пересечения графиков. Представив уравнение x³-x-1=0 в виде x³=x+1, и построив график правой и левой части, можно с уверенностью сказать, что корень находится на участке от 1 до 2. К недостаткам метода можно отнести необходимость строить график, а также то, что графики могут пересекаться под острыми углами, что может усложнить изоляцию корня.

4. Границы корней алгебраического уравнения.

Теорема 2. Алгебраическое уравнение n-ной степени f(x)= имеет ровно n корней , действительных и комплексных, при условии, что каждый корень считается столько раз, какова его кратность.

Для таких уравнений задача нахождения границ корней решается более просто и точно, чем для трансцендентных уравнений.

Теорема 3 (о кольце). Пусть a=max{|a_i|} i=1…n и a'=max{|a_i|} i=0…n-1. Тогда действительные корни уравнения (1) лежат в интервале r<|x|<R, где r= , R=1+

Доказательство базируется на свойствах сумм числовых рядов, мажорируемых геометрическими прогрессиями со знаменателем меньше единицы.

Замечание: В общем случае, корень x может быть и комплексным, т. е. x=ξ+iη |x|= значит, на комплексной плоскости ξ0η корни расположены в кольце.

Эта теорема работает для первого этапа нахождения корней.

5. Приближенное значение корня и его оценка.

Неточность значения полученного корня имеет три причины, определяемые существованием трех видов погрешностей. Это неустранимая погрешность (погрешность постановки задачи), вычислительная погрешность (конечное число знаков в разрядной сетке ЭВМ, округление) и погрешность метода.

Сами методы делятся на точные и приближенные. Под точными следует понимать методы, имеющие жесткий алгоритм и критерий нахождения результата – окончания алгоритма. Время решения однотипных задач по таким алгоритмам одинаково. Приближенные алгоритмы – это, как правило, алгоритмы последовательного приближения. Время решения задачи зависит от исходных данных и заданной погрешности вычислений. Критерий нахождения результата – достижение заданной точности. Иногда приближенные алгоритмы дают более точный результат, чем "точные" (сказывается вычислительная погрешность).

Пусть точным корнем уравнения (1) является ξ, а в результате применения нами некоторого метода получено значение корня . Вопрос: как оценить погрешность знания нами , не зная ξ. В этом случае применима оценка сверху для модуля ошибки – априорная оценка, т. е. оценка до получения результата.

Теорема 4 об оценке приближенного решения.

Если ξ – точный, а – приближенный корень уравнения (1), находящиеся на отрезке [a; b], и  x из [a; b] |f'(x)|≥m>0, то справедлива формула | -ξ|≤ (4). В частности, может быть m= |f'(x)|. Инфимум – точная нижняя граница отрезка.

Доказательство (базируется на теореме Лагранжа)

Если f'(x) непрерывна на (a; b) то существует *:f'( *)= (теорема Лагранжа). По теореме Лагранже на промежутке ( ; ξ) можно записать f( )-f(ξ)=( -ξ)•f'(x*), где x*( ; ξ) Т. к. f(ξ)=0, то -ξ=  | -ξ|= .

Т. к. m= |f'(x)|<f'(x*) и ( ; ξ)(a; b)  | -ξ|≤ . Теорема доказана.

На практике часто точность x оценивается малостью значения f(x). Это неверно. Уравнение (1) эквивалентно уравнению Nf(x)=0, где N=const и погрешность f(x) можно сделать сколь угодно большой или малой в зависимости от N.

6. Метод проб.

Из формулы оценки погрешности следует, что погрешность будет тем меньше, чем меньше сам отрезок [a; b]. Если, зная отрезок [a_k; b_k] содержащий корень ξ, мы сможем указать отрезок [a_k+1; b_k+1], также содержащий корень ξ и такой, что b_k-a_k>b_k+1-a_k+1; a_k≤a_k+1≤ξ≤b_k+1≤b_k то процесс построения отрезка [a_k+1; b_k+1] будет называться уточнением корня. Уточнение корня повторяется до тех пор, пока не будет получен отрезок [a_k+1; b_k+1], обеспечивающий требуемую точность. Все такие методы называются итеративными. Если при этом с ростом k a_k→ξ или b_k→ξ, то процесс называется сходящимся.

Рассмотрим метод проб.

Пусть выделен промежуток (a; b), содержащий все или несколько (не обязательно один) корней уравнения (1). Разобьем отрезок на n частей x₀=x; x₁=x+h; x₂=x+2h…x_n=x+nh=b, где h= и будем исследовать знак произведения sign[f(x_i)]•sign[f(x_i+1)]. Как только получится "-", вернемся на шаг назад и исследуем отрезок [x_i; x_i+1] с более мелким шагом x_i; x_i+h₁; x_i+2h₁…x_i+n₁h₁=x_i+1, где h₁= . Следим за значением sign[f(x_i+kh₁)]•sign[f(x_i+(k+1)h₁)] и т. д. до получения заданной точности. После получения очередного корня движемся вперед с прежним шагом h.

Замечание: число точек деления не следует брать большим (теряется скорость) или малым (можно потерять корни). Количество вычислений заранее предсказать нельзя.

Допустим, что уравнение (1) имеет на промежутке (0; 1) один корень. Точность вычислений ε=10^-3. При n=1000 количество вычислений f(x) будет от 2 до 1001. Если же взять n=n₁=n₂=10, то количество вычислений f(x) будет от 4 до 29.

Метод проб используют, как правило, для отделения корней.

7. Метод деления пополам (половинного деления).

Метод применим для уточнения корней. При этом задана функция, отрезок; функция монотонна и на концах отрезка принимает значения разных знаков.

Шаг 1: Находим центр x=

Шаг 2: Если f( )≡0 , то – корень. Иначе отрезок разбивается точкой на два и выбирается для дальнейшего рассмотрения тот, для которого f(a₁)•f(b₁)<0

Шаг 3: Снова выполняем шаг 1.

Получается последовательность интервалов (a; b), (a₁; b₁) (a₂; b₂)…(a_n; b_n)…

b_n-a_n= (b-a) (5)

f(a_n)•f(b_n)<0 (6)

a≤a₁≤a₂≤…≤a_n≤ξ≤b_n≤…≤b₂≤b₁≤b

ξ:f(ξ)=0

{a_i} – неубывающая и ограничена сверху

{b_i} – невозрастающая и ограничена снизу

По теореме о существовании предела числовой последовательности, существуют конечные пределы {a_i} и {b_i}. В силу (5) они равны и равны ξ.

В силу (6) (f(a_n)•f(b_n))=f²(ξ)≤0  f(ξ)=0  ξ – корень.

Метод сходится всегда. a_n – приближенное значение корня с недостатком, b_n – с избытком. По формуле (5) можно определить трудоемкость вычислительного процесса для достижения требуемой точности.

Метод быстрее метода проб, но ищет только один корень (т. е. неуниверсален).

8. Метод простой итерации.

Пусть уравнение (1) представлено в виде x=φ(x) (7)

Предположим следующий вычислительный процесс.

Шаг 1: зададим x=x₀ из (a; b)

Шаг 2: вычислим по заданному x правую часть (7), т. е. φ(x)

Шаг 3: полученный результат будем считать приближенным значением корня x₁. x₁=φ(x)

Шаг 4: вернемся на шаг 1, считая x₀=x₁

В результате вычислений будет получена последовательность x₀, x₁, x₂…x_n. Если эта последовательность сходится, т. е. у этой последовательности существует конечный предел, то этот предел будет корнем уравнения (7), а значит и уравнения (1).

Можно показать, что сходимость обеспечивается малой крутизной графика φ(x).

9. Условие сходимости итеративного процесса.

Достаточное условие сходимости дается в следующей теореме.

Теорема 5. Пусть функции φ'(x) и φ(x) непрерывны на промежутке (a; b). Тогда, если существует правильная дробь k:  x(a; b) |φ'(x)|≤k<1 (*), то процесс итераций x_n+1=φ(x_n) сходится при любом x₀ из (a; b). Кроме того, предел x_n является единственным корнем уравнения (7) на (a; b).

Доказательство.

Доказательство сходимости базируется на теореме Лагранжа и свойствах сумм числовых рядов, мажорируемых геометрической прогрессией со знаменателем k. Единственность корня доказывается от противного.

10. Оценка приближений в методе итераций.

1 способ.

Используя теорему 4, можно записать |ξ-x_n|≤ , где m= |f'(x)|

2 способ.

Оценка скорости сходимости.

|x_n+l-x_n|≤|x_n+l-x_n+l-1|+|x_n+l-1-x_n+l-2|+…+|x_n+1-x_n|≤k^n+l-1•|x₁-x₀|+k^n+l-2•|x₁-x₀|+…+kⁿ•|x₁-x₀|=|x₁-x₀|•kⁿ•(1+k+…+k^l-1)= =|x₁-x₀|•kⁿ• при l→∞ |ξ-x_n|≤|x₁-x₀|• .

Таким образом, зная первое приближение и k (по (*)), можно оценить число итераций n, исходя из заданной погрешности.

Оценка точности приближений.

|x_n+l-x_n|≤|x_n+l-x_n+l-1|+|x_n+l-1-x_n+l-2|+…+|x_n+1-x_n|≤k^l•|x_n+1-x_n|+k^l-1•|x_n+1-x_n|+…+k•|x_n+1-x_n|=|x_n+1-x_n|•k•(1+k+…+k^l-1)= =k•|x_n+1-x_n|• при l→∞ |ξ-x_n|≤|x_n-x_n-1|• .

При k≈0,5 |ξ-x_n|≤|x_n-x_n-1| если |x_n-x_n-1|<ε, то и |ξ-x_n|<ε. Таким образом, если приближения отличаются мало (в пределах заданной погрешности), то за корень принимаем найденное приближение. В общем случае, это неверно при k≈1.

11. Преобразование уравнения (1) к виду (7).

Любое уравнение вида (1) можно записать в виде (7), но для сходимости метода итераций необходимо выполнение условия (*). Общих рецептов приведения (1) к виду (7) наилучшим образом с точки зрения скорейшей сходимости и простоты вычислений не существует. Но существует общий способ, при котором сходимость будет обеспечена.

Если есть f(x)=0, то можно записать λ•f(x)=0, где λ=const.

Пусть 0<m≤f'(x)≤M<∞; x(a; b); m= f'(x); M= f'(x); Супремум – точная верхняя граница отрезка. Если f'(x)<0, то заменим уравнение (1) уравнением –f(x)=0.

Если λ•f(x)=0, то можно записать x=x-λ•f(x), или φ(x)=x-λ•f(x). Тогда из (*) φ'(x)=1-λ•f'(x). Очевидно, что 0≤φ'(x)=1-λ•f'(x)≤k<1.

Т. е. 0≤1-λ•M≤1-λm≤k<1. Выберем λ= , получим 0≤1- ≤k<1. Таким образом, условие сходимости выполняется.

12. Метод Ньютона.

Метод Ньютона является весьма общим. Он применим не только для решения нелинейных уравнений, но и их систем.

Пусть дано некоторое уравнение вида (1) и некоторый участок (a; b) изолированности корня. Выберем какую-либо точку x₀(a; b) Рассмотрим разность δ=ξ-x₀. Пусть δ – малая величина. ξ=x₀+δ.

Разложим f(ξ) в ряд Тейлора в точке x₀ f(ξ)=f(x₀+δ)=f(x₀)+δ•f'(x₀)+O(δ²); f(x₀)+δf'(x₀)≈0.

Решая это уравнение, мы определим не точное значение погрешности δ, а приближенное значение δ₀.

δ₀=- . Можно предположить, что если δ=ξ-x₀, то δ₀=x₁-x₀, т. е. x₁=x₀- .

В общем случае, x_n+1=x_n- (11).

Если все x_n принадлежат области определения функции, и x_n(a; b) f'(x)≠0, то такой процесс можно построить. Такой же результат можно получить, если рассмотреть касательные к графику функции f(x). Поэтому метод Ньютона иначе называется методом касательных. Можно заметить, что в качестве начального приближения нужно брать точку, в которой кривизна f''(x₀) и значение функции f(x₀) одного знака, т. е. f''(x₀)•f(x₀)>0

Теорема 6.

Если f(a)•f(b)<0, f'(x) и f''(x) непрерывны, не равны нулю и сохраняют знак x(a; b), то по начальному приближению x₀, такому, что f(x₀)•f''(x₀)>0, можно вычислить корень уравнения (1) по методу Ньютона по формуле (11) с любой заданной степенью точности.

Модификация метода Ньютона.

Если f'(x) на (a; b) изменяется мало, то f'(x)≈f'(x₀) и формула (11) запишется в виде x_n+1=x_n- . Геометрически, это означает, что приближения делаются с помощью линий, параллельных первой касательной.

13. Метод хорд

Пусть дано некоторое уравнение вида (1) и некоторый участок (a; b) изолированности корня. Предположим, что f(x) на (a, b), близка к линейной. Проведем хорду, соединяющую значения f(a) и f(b). Пересечение хорды с осью Ox будем считать приближенным корнем. Можно показать (с помощью подобия треугольников), что x₁=b- •f(b).

Проведем следующую хорду и определим следующее приближение x₂.

x₂=x₁- •f(x₁).

Таким образом, рабочая формула метода x_n+1=x_n- •f(x_n) (12), x₀=b или x_n+1=x_n- •f(x_n) (12'), x₀=a.

Обобщая (12) и (12'), получим x_n+1=x_n- •f(x_n) (13).

Теорема 7.

Если f(a)•f(b)<0, f'(x) и f''(x) непрерывны и сохраняют знак x(a; b), то, взяв в качестве x значение, удовлетворяющее f(x)•f''(x)>0, а в качестве начального приближения значение x₀, удовлетворяющее f(x₀)•f'(x₀)<0, можно вычислить корень уравнения (1) по методу хорд с помощью формулы (13) с любой степенью точности.