Пусть система линейных алгебраических уравнений приведена к виду

.

Запишем систему в развернутом виде:

(4.38)

…………………………………………

В методе простой итерации приближение Х^(к+1) вычисляется по предыдущему приближению Х^(к) путем постановки компонента Х^(к) в правую часть всех уравнений системы (4.38), т.е.

.

Метод Зейделя (Ф. Зейдель (1821 – 1896) – немецкий математик) напоминает метод простой итерации. Отличие заключается в том, что при вычислении (к+1) –го приближения для компоненты x_i учитываются уже вычисленные ранее (к+1) –е приближение для компонент х₁, х₂, …, х_i-1. Вычисления производятся по формулам:

(4.39)

…………………………………………………………..

таким образом,

(4.40)

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

Теорема. Для сходимости метода Зейделя достаточно, чтобы выполнялось одно из условий:

1.)

2.) .

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

Пример. Методом Зейделя решить систему уравнений

Приведем заданную систему к виду

В качестве Х⁽⁰⁾ выбираем столбец свободных членов. Вычисления оформляем в виде табл. 4.6. В качестве ответа берем последнюю строку этой таблицы.

Таблица 4.6

	0.6	0.6	1.875
	0.855	0.021	1.981875
	0.992176	-0.005685	1.999021
	0.998667	0.000125	1.999833
	0.999941	0.000055	1.999992

Этот же пример был решен при помощи метода простой итерации. Сравнивая полученные значения с точным отвктом (х₁=1; х₂=0; х₃=2), видим, что метод Зейделя в данном случае дает лучшую сходимость, чем метод простой итерации.

Глава 5. ОБРАБОТКА РЕЗУЛЬТАТОВ НАБЛЮДЕНИЙ

МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

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

Пусть в результате некоторого эксперимента получена таблица значений функции y=f(x):

x	x0	x1	…	хn
y	y0	y1	…	yn

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

у=F(x, a₀, a₁, …, a_m), (5.1)

Где a₀, a₁, …, a_m - неизвестные параметры.

Числовые параметры желательно подбирать так, чтобы полученная кривая достаточно хорошо соответствовала исходным данным. Таким образом, нужно указать критерий, согласно которому та или иная кривая является достаточно “хорошим” приближением к исходным данным. Обозначим через у^/_i значения функции, вычисленные по эмпирической формуле (5.1) в заданных точках х_i, т.е.

y^/_i=F(x_i, a₀, a₁, …, a_m), .

Назовем уклонениями эмпирической формулы (5.1) от исходных данных («невязкими») разности

.

Вопрос о том, является ли кривая достаточно “хорошим” приближением к экспериментальным данным, можно поставить следующим образом: какое условие необходимо наложить на уклоненния точек от кривой, чтобы эта кривая представляла экспериментальные данные достаточно хорошо? Казалось бы, что наиболее простое и логичное условие состоит в том, чтобы сумма уклонений точек от кривой, т.е. , была наименьшей.

На рис.5.1 сумма уклонений равна нулю, однако проведенную прямую никак нельзя признать удовлетворительным приближением к экспериментальным данным.

у

А(х₀, у₀)

В(х₁, у₁₎

х

Рис. 5.1.

Можно попытаться обойти это затруднение, используя в критерии сумму абсолютных величин уклонений, т.е. требуя, чтобы

стала минимальной. Но в данном случае для нахождения этого минимума нельзя воспользоваться дифференцированием,так как абсолютная величина не имеет производной в точке минимума. Поэтому на практике в таких случаях чаще всего используют так называемый метод наименьших квадратов, согласно которому ищем те значения параметров а₀, а₁, …, а_m, при которых сумма квадратов уклонений

принимает минимальное значение. Другими словами, параметры а₀, а₁, …, а_m находим из условия обращения в минимум выражения

. (5.2)

Отсюда, используя необходимые условия существования экстремума функции нескольких переменных, получаем систему уравнений для определения неизвестных а₀, а₁, …, а_m:

. (5.3)

Если система (5.3) имеет единственное решение, оно будет искомым.

На практике эмпирическую формулу чаще всего строят в виде алгебраического многочлена.

5.2. Приближение функции, заданной таблично,

алгебраическими многочленами по методу наименьших квадратов

Предположим, что по опытным данным

х	x0	x1	…	xn
у	y0	y1	…	yn

требуется построить эмпирическую формулу в виде многочлена степени m (m<n):

P_m(x)=a₀+a₁x+…+a_mx^m.

Составляем S(a₀, a₁, a₂, …, a_m) по формуле (5.2):

. (5.4)

Система уравнений для определения параметров a₀, a₁, a₂, …, a_m (5.3) запишется в данном случае в следующем виде:

. (5.5)

Система (5.5) состоит из (m+1)-го уравнения с (m+1)-м неизвестным. Можно показать, что определитель этой системы отличен от нуля, так что ситема имеет единственное решение, при котором S принимает свое минимальное значение.

Рассмотрим частные случаи наиболее часто встречающиеся на практике.

1. Пусть m=1, т.е. функцию аппроксимируем многочленом первой степени

P₁(x)=a₀+a₁x.

Составляем

.

Записываем систему (5.5) для нахождения параметров а₀ и а₁:

Преобразуем эту систему:

(5.6)

Решив ее, находим а₀ и а₁.

2. Пусть m=2, т.е. функцию аппроксимируем многочленом второй степени

P₂(x)=b₀+b₁x+b₂x².

В этом случае

.

Составляем систему для нахождения параметров b₀, b₁, b₂:

Преобразуем полученную систему:

(5.7)

Решив эту систему, найдем b₀, b₁, b₂.

Все вычисления коэффициентов систем (5.6) и (5.7) удобно расположить в виде таблицы 5.1

Таблица 5.1

i	xi	xi2	xi3	xi4	yi	xiyi	xi2yi
. . . n	x0 x1 . . . xn	x02 x12 . . . xn2	x03 x13 . . . xn3	x04 x14 . . . xn4	y0 y1 . . . yn	x0y0 x1y1 . . . xnyn	x02y0 x12y1 . . . xn2yn

Отметим, что задача построения эмпирической формулы отлична от задачи интерполирования. Сравним их.

Обычно в результате эксперимента получаются большие таблицы. На практике же применяются интерполяционные многочлены невысоких степеней. Если, например, строится интерполяционный многочлен степени m, то их таблицы используется (m+1) точка, остальные точки при этом не учитываются. При построении аппроксимирующего многочлена степени m по методу наименьших квадратов используются все точки таблицы, что дает более полную информацию об исходной функции. Кроме того, исходные данные х_i и y_i, как правило, являются приближенными и содержат ошибки. Интерполяционный многочлен, совпадающий в узлах интерполяции с интерполируемой функцией, повторяет эти ошибки. Аппроксимирующий многочлен, построенный по методу наименьших квадратов, сглаживает отдельные ошибки и поэтому лучше отображает действительность. Эти замечания справедливы не только для многочленов, но и для интерполяционной и эмпирической функций любого вида.

Метод наименьших квадратов с конца ХVIII века является одним из самых эффективных и распространенных методов математической обработки результатов наблюдений и опытов.

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

Глава 6. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ

ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

6.1. Методы решения задачи Коши. Вводные замечания

В вычислительной практике довольно часто приходится иметь дело с задачами для обыкновенных дифференциальных уравнений. Задача решения обыкновенного дифференциального уравнения сложнее задачи вычисления интеграла, и доля задач, решаемых в явном виде здесь ничтожно мала. Обычно приходится прибегать к помощи приближенных методов решения подобных задач. Конкретный вид метода зависит прежде всего от типа решаемой дифференциальной задачи. Наиболее простой и важной для приложений является задача Коши.

Рассмотрим случай одного обыкновенного дифференциального уравнения первого порядка. Методы, которые мы рассмотрим, легко обобщаются для системы дифференциальных уравнений первого порядка и для дифференциальных уравнений высших порядков. Итак, рассмотрим задачу Коши для дифференциального уравнения первого порядка.

Пусть на отрезке требуется найти решение у(х) дифференциального уравнения

, (6.1)

удовлетворяющее при начальному условию

, (6.2)

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

Выбираем на отрезке фиксированные точки

. (6.3)

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

.

Большое количество методов решения задачи Коши имеет расчетную формулу вида

, (6.4)

где F – некоторая известная функция указанных аргументов определяемая способом построения метода и зависящая от уравнения (6.1) и избранной сетки (6.3).

При q=0 формула (6.4) записывается в виде

. (6.5)

Методы такого типа называются одношаговыми. При получаем многошаговые методы.

Если применяется одношаговый метод, то вычисления при помощи этого метода по формуле (6.5) можно начинать со значения n=0. При применении многошагового метода вычисления по формуле (6.4) можно начинать только со значения n=q. Первые q значений y₁, y₂, …,y_q приближенного решения вычисляются при помощи какого-либо другого метода, что влечет за собой нарушение однородности вычислительного процесса. Одношаговые методы в этом отношении являются предпочтительнее. Удобнее ими пользоваться и в том случае, когда шаг сетки не является постоянным для всех значений n.

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

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

На практике эти два метода необходимо сочетать, учитывая их достоинства и недостатки.

6.2. Решение дифференциальных уравнений

с помощью рядов Тейлора

Предположим, что процесс решения задачи (6.1), (6.2) доведен до некоторой точки и известно (точно или приближенно) соответствующее значение искомого решения в очередной точке сетки:

.

Напишем разложение функции y(x) в ряд Тейлора в окрестности точки ;

Подставляя в полученное разложение x =x_n+1 и обозначая y^(j)(x_n)=y_n^(j), получим

. (6.6)

Отсюда

. (6.7)

Нахождение решения с помощью ряда Тейлора является одношаговым методом, так как для вычисления у_n+1 требуется информация только об одной предыдущей точке х_n, y_n.

Если решение уравнения (6.1) имеет на отрезке непрерывную производную порядка (m+1), погрешность приближенного равенства (6.7) будет величиной порядка . При достаточно малых h и больших m погрешность будет величиной достаточно малой. Для применения формулы (6.7) необходимо вычислить производные, входящие в правую часть формулы. Исходное уравнение записывается в виде

.

Отсюда

. (6.8)

Дифференцируя заданное уравнение по х, получим

. (6.9)

Отсюда

, (6.10)

где значения функции f(x,y) и ее производных вычисляются при x=x_n, y=y_n.

Дифференцируя (6.9) по х и подставляя сюда x=x_n, y=y_n, получим

(6.11)

где значения функции f(x,y) и ее производных вычисляются при x=x_n, y=y_n.

Очевидно, что с ростом порядка производных выражения для их вычисления становятся все более громоздкими, поэтому при m>1 формула (6.7) редко применяется на практике. При использовании ЭВМ применение этого метода требует написания большого числа блоков вычисления производных, что приводит к большим затратам машинного времени. На практике в основном применяются методы, не требующие нахождения значений производных от правых частей уравнений.

Таким образом, с точки зрения практических вычислений этот метод обычно неудобен. Однако при сравнении различных практически применяемых методов для их оценки есть некоторый критерий – насколько тот или иной метод согласуется с разложением в ряд Тейлора. Подставляя в (6.6) выражения для , , (формулы (6.8), (6.10), (6.11)), получим

, (6.12)

где значения функции f(x,y) и ее производных вычисляются при x=x_n, y=y_n.

6.3. Метод Эйлера