Выч.мат

где x и y подбираются так, чтобы минимизировать погрешность.

Подставим (11) в (10):

yn+1 = yn + hf (xn , yn )+ 21 h[f (x, y)− f (xn , yn )].

В общем виде последнее соотношение можно записать следующим образом:

Выберем параметры α, β,γ,δ так, чтобы разложение выражения

(12) в ряд Тейлора было максимально близко к (10). Разлагаем правую часть (12):

yn+1 = yn + h(α + β )f (xn , yn )+αh2 (γ f x′ +δf y′ )

Сравнивая с

В результате получаем однопараметрическое семейство схем Рун- ге-Кутта

yn+1 = yn + h (1 −α)f (xn , yn )+α f xn + 2hα , yn + 2hα fn .

Эта схема имеет одношаговую погрешность O(h3 ).

Придавая параметру α конкретные значения, получаем различные схемы решения задачи Коши. При α = 1 имеем

62

yn+1 = yn + hf xn + h2 , yn + h2 fn

и таким образом, эта схема Рунге-Кутта дает в точности выражение (9) процедуры дробных шагов.

При значенииα =12 получаем следующую схему

Эта формула может быть получена и другим способом, если интеграл в соотношении (6) вычислять по формуле трапеций.

Задачи

1. Определить вид функции f(x,y), для которой метод Эйлера решения уравнения

dydx = f (x, y)

имеет второй порядок точности, если f непрерывна вместе со своими вторыми производными.

3. Показать, что для уравнения y′ = f (x, y) погрешность приближенного решения методом Адамса

yn+1 = yn + h 32 f (xn , yn ) − 21 f (xn−1 , yn−1 ) yn−1 = yn − hfn , имеет второй порядок точности.

4. Методом Эйлера численно решить задачу Коши на отрезке [a,b] с шагом h = 0.1

63

5. Методом Эйлера по схеме дробного шага решить уравнение на

[a, b] с шагом h = 0.1

6. Методом Рунге - Кутта по формуле (13) решить задачу Коши на отрезке [a,b] с шагом h = 0.1

7. С использованием метода Эйлера построить процесс численного

решения задачи Коши для уравнения 3 порядка

a0 y′′′ + a1 y′′ + a2 y′ + a3 y = f (x), y = y(x), x [0,1]

с шагом h. Величины ai и bi являются константами, f(x) – известная функция.

8.Показать, что формулу Эйлера можно получить, если численно проинтегрировать (1) с использованием формулы прямоугольников.

9.Получить формулу (13), численно интегрируя (1) с помощью формулы трапеций.

Ответы и указания к задачам.

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

64

матриц небольшого размера выгодны только прямые методы. Итерационные методы в настоящее время используются при n ≥ 10000 и для матриц специального вида.

1. Решение систем линейных уравнений методом исключения Гаусса (компактная схема)

Этот метод относится к точным методам. Для его численной реализации требуется выполнить ~ 2n3/3 арифметических операций, где n

– размерность матрицы.

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

где aij ≡ aij(0) , bi ≡ bi(0) .

1). Первый этап, i = 1 , первое уравнение (2) делится на a11(0), а пре-

образованные значения матрицы А и вектора b снабжаются верхним индексом (1):

Из (3) получаем a11(1) = 1 , и первое уравнение приобретает вид

x1 + ∑n a1(1j) x j = b1(1). j=2

Все остальные уравнения преобразуются следующим образом: из i- го уравнения вычитается первое, умноженное на элемент первого

столбца ai1(0):

При этом из (4) очевидно, что во всех строчках матрицы aij(1) (на-

чиная со второй) первого столбца расположены нули:

66

ai1(1) = ai1(0) −ai1(0)a11(1) = 0 .

Таким образом, на первом этапе матрица приобретает вид

2). Второй этап, i = 2 . Первая строка новой системы остается без изменений. Вначале второе уравнение делится на a22(1)

Здесь новые значения матрицы снабжены новым индексом (2) и очевидно, что a22(2) = 1 . Далее аналогично соотношениям (4) преобразуем остальные элементы расширенной матрицы

В результате во втором столбце матрицы aij(2)под главной диагона-

лью имеем нулевые элементы:

ai(22) = ai(21) − ai(21)a22(2) =0 ,

а второе уравнение записывается в форме

x2 + ∑n a2(2j) x j = b2(2). j=3

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

k) i=k. На k-ом этапе k-ая строчка делится на диагональный элемент этой строки:

67

причем во всех строчках k-го столбца стоят нули:

aik(k ) = aik(k −1) − aik(k −1)akk(k ) = 0 i ≥ k + 1 .

Следовательно, на этом этапе матрица А принимает вид

Наконец, на заключительном n-ом этапе после деления n-ой строки на диагональный элемент система приводится к требуемой форме с треугольной матрицей:

Последнее соотношение можно записать в следующем виде

j=i+1

Эта фаза решения (приведения матрицы к треугольному виду) называется прямым ходом метода Гаусса. На этой фазе отыскания

68

решения фактически определяются коэффициенты преобразованной системы уравнений aij(k ) и bk(k ) , и формулы (7) называются

формулами прямого хода метода Гаусса. Как только эти коэффициенты вычислены, легко находится решение на обратном ходе ме-

тода Гаусса с помощью (8).

Действительно, из последнего уравнения находим xn = bn(n), из

j=k +1

Выражения (9) называются формулами обратного хода метода Гаусса.

Пример. Решить систему уравнений x1 + 2x2 + 3x3 + 4x4 = 10 2x1 + 3x2 + 4x3 + x4 = 10 3x1 + 4x2 + x3 + 2x4 = 10 4x1 + x2 + 2x3 + 3x4 = 10

Решение. Составим таблицы для каждого этапа метода Гаусса. На первом шаге таблица составляется следующим образом. В столбцы поместим следующие данные: в первый – номер уравнения, во второй – коэффициенты, на которые следует умножить первое уравнение, чтобы в соответствующей строке исключить элемент первого столбца матрицы. В столбцах 3 − 7 размещаются элементы расширенной матрицы.

После умножения первой строки на 2 (3) (4) и вычитания ее из второй, (третьей), (четвертой) строк получаем следующую таблицу:

69

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

Чтобы исключить из последней строки элемент третьего столбца матрицы достаточно к четвертой строчке прибавить третью:

В результате прямого хода получен главный результат метода Гаусса – матрица aij приведена к треугольному виду. В процедуре обратного хода находим решение. Из последней строки имеем x4 = 1. Третья строчка дает x3 = x4 = 1. Последующие вычисления на обратном ходе дают x2 = 1, x1 = 1.

1.1. Метод Гаусса с выбором главного элемента.. При последова-

тельном исключении неизвестных элементы каждой строки aik(i)

приходится делить на диагональный элемент aii(i). В том случае,

если это число мало, то очень велика погрешность от деления, приводящая к сильному искажению результата. Чтобы избежать этого, процесс исключения проводят с выбором главного элемента в строке (или в столбце). Подобная процедура выполняется, если в компактной схеме Гаусса на диагонали встретился нулевой элемент. Суть этой процедуры состоит в следующем. Пусть после k шагов система приобрела вид:

70