Методы Рунге — Кутта

Методы Рунге — Кутта.

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

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

Точки - известны.

Проведём через касательную:

1) По условию

Ошибка:

2) Через точку проведём касательную :

Ошибка и так далее.

Исправленный метод Эйлера:

где , то есть

Модифицированный метод Эйлера.

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

Точка - известна.

Проведём через касательную , где .

Так как по условию:

Откуда .

Ошибка равна , затем , так как

Исправленный метод Эйлера

Через проведём

Через проведём

Затем

Метод Рунге – Кутта 4-го порядка.

Программы:

Sub Euler ()

Dim x As Single ' начальное значение

Dim x1 As Single ' конечное значение

Dim N As Integer ' число шагов

Dim Y As Single ' начальное значение функции

Dim H As Single ' шаг интегрирования

H = (x1 – x) / N: y1 = y

For i = 1 to N

Call funk (x, f): f1 = f

x = x + h: y = y + f * h: call funk (x, f)

y = y1 + h * (f1 + f) / 2: y1 = y

next i

sub funk (x, f)

f = - exp (- x)

end sub

y’ =

y = - точное

y (2) = 0, – метод Эйлера

Модифицированный метод Эйлера.

h = (x1 - x) / N/2: y1 = y

for i = 1 to n

call funk (x, f )

x = x + h: y = y + f * h: call funk (x, f)

y1

Модифицируемый метод Эйлера

ym+n = ym + h[f(xm+, ym + f(xm, ym)]

h = (x1 – x)/N/2 : y1 = y

for i = 1 to n

call funk(x, f)

x = x + h: y = y + f * h: call funk(x, f)

y1 = y1 + f * 2 * h : x = x + h : y = y1

next i

y(2) = ,

Усовершенствованный метод последовательный приближений

f(xn-1) = xn; f(xn) = xn+1

∆x = xn-1 – xn = f(xn) - xn

xn+1 = xn + ∆x, лучше взять xn+1 = xn + λ *∆x, λ>1

tg =

tg = , где xn

f'() =

—известно, но можно принять

f'(

Геометрический процесс отыскания следующего приближения xn-1 сводится к тому, что проводится хорда через точки (xn, f(xn)) и (xn-1, f(xn-1)) и определяется точка ее пересечения с прямой y = x.

Сходимость:

1) 0<f'(x)<1 1<<

поправки ∆x малы, но 1<< увеличит их и сходимость улучшиться

2) -1<f'(x)<0

поправки велики, а их уменьшит и метод сходится быстрее: поправки уменьшаются на коэффициент между и 1.

Расходится:

3) f'(x)>1

Так как , то в усовершенствованном методе знаки поправок изменяются нужным образом.

4) f'(x)<-1 0< — расходится, так как поправки велики

Каждая поправка умножается на коэффициент между 0 и и процесс расходится.

Описанная модификация метода итераций принадлежит Векштейну (1958 г)

Метод Ньютона – Рафсона

Пусть xn и

Если , то метод сходится:

Так как f (x) = x, (F (x) = 0 = x – f (x)), то для x, близких к «a», (f (x) - x) – мало. Поэтому (1) сходится, если:

1) выбрано близко к решению x = f (x)

2) f ''(x) – не становится слишком большой.

3) f ' (x) не слишком близка к 1.

Это и есть знаменитый метод Ньютона – Рафсона.

F (x) = x – f (x) = 0

Или:

1) близко к корню F (x) = 0

2) - не слишком большая

3) - не близка к нулю

«3)» означает, что никакие два корня не находятся слишком близко один к другому.

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

а) , то есть равен углу наклона касательной к y = f (x) в точке

б)

Уравнение касательной:

Пусть

выбирать так, чтобы

Пример:

F (x) = sin x – x + 0.15 = 0 на отрезке [0.5; 1] с погрешностью

То необходимо найти чтобы

Это верно при = 1

на [0.5; 1]

Примечание: если , то можно

1)

2)

3) Вычисляем

4) Проверяем и так далее.

Случай почти равных корней

Производная близка к 1 при

На основании теоремы о среднем

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

Трудности возникают, так как

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

Пусть - решение. Эта точка

Положим для начального приближения

Пусть

Разложим f (x) в ряд Тейлора в окрестности точки

Так как

Пусть

Но по условию

Если , так как надо решить уравнение

Сначала решаем:

Потом ищется:

Затем начальные приближения для

Если , то это означает что имеет более чем один корень вблизи , тогда сначала решается уравнение , то это означает, что имеет более чем один корень .

Метод хорд

Каждое значение xn+1 находится как точка пересечения оси абсцисс с хордой, проведенной через точки F(a) и F(b) , причем одна из этих точек фиксируется — та, для которой F(x)·F''(x)>0.

Если неподвижен конец хорды x = a, то

xn+1 = xn -

Если неподвижен конец хорды x = b, то

xn+1 = xn -

Если |xn+1 - xn|>,то в первом случае считаем b = xn+1, во втором a = xn+1 и повторяем вычисление.

При использовании метода хорд полагается, что корень находится на отрезке [a, b].

Метод секущих

Реализуется алгоритмом, описанным выше, если абсцисса a и b взяты с одной стороны от корня.

Необходимость вычисления F'(x) и выбора одной из двух формул затрудняют практическое применение методов хорд и секущих в отдельности.

Полином Чебышева

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

Свойства полиномов Чебышева

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

Все эти свойства образуют аппроксимирующую функцию минимакс (то есть в процессе аппроксимации минимизируется максимальная ошибка)

В МНК минимизируется сумма квадратов ошибок. В МНК максимальная ошибка может принимать достаточно большое значение. В аппроксимации Чебышева средняя ошибка часто может принимать большое значение, а минимизируется максимальная ошибка.

Определение полиномов Чебышева

T0(x) = 1

Tn(x) = Cos(n)

Cos = x

Полиномы Чебышева ортогональны, так как косинус является ортогональной функцией и Cos(n) является полиномом в степени n величин .

Cos(n+1) + Cos(n-1) = 2CosCosn

Tn+1 + Tn-1 = 2xTn

Tn+1 = 2xTn - Tn-1

Так как T0 = 1; T1= x, то T2 = 2xT1 – T0 = 2x2 – 1

T3 = 2xT2 - T1 = 2x(2x2 – 1) – x = 4x3 – 3x

То есть T0 = 1

T1 = x

T2 = 2x2 – 1

T3 = 4x3 – 3x

T4 = 8x4 – 8x2 +1

T5 = 16x5 – 20x3 +5x

T6 = 32x6 – 48x4 + 18x2 -1

T7 = 64x7 – 111x5 +56x3 -7x

T8 = 128x8 – 256x6 +160x4 – 32x2 +1

Можно образовать таблицу степеней x в выражения полиномов Чебышева, проводя решение относительно степеней x из этой таблицы:

1 = T0

x = T1

x2 = (T0 + T2)/2

x3 = (3T1 + T3)/4

x4 = (3T0 + 4T2 + T4)/8

x5 = (10T1 + 5T3 + T5)/16

x6 = (10T0 + 15T2 + 6T4 + T6)/32

x7 = (35T1 + 21T3 + 7T5 + T7)/64

x8 = (35T0 + 56T2 + 28T4 + 8T6 + T8)/128

Важное свойство полиномов Чебышева заключается в том, что во всех полиномах степени n имеется коэффициент определение 1 и это полиномы Чебышева при делении на 2n-1 обладают наименьшим экстремальным значением в интервале -1 x+1

Не существует других полиномов степени n, эти коэффициенты равны 1 и которые обладают меньшим экстремальным значением, чем

max в интервале |x|1

Это является важным положением, так как утверждает, что если аппроксимировать функцию на интервале |x|1 при помощи полиномов Чебышева, ограниченных n членами, максимальной ошибкой приближения будет 1/2n-1

Разложим функцию f(x) в ряд с помощью полиномов Чебышева:

f(x) =

Метод аппроксимации f(x) с помощью полиномов Чебышева является простым в употреблении и обладает умеренной сходимостью любого ограниченного разложения функции f(x) в ряд.

Так как f(x) = , то

f(x) = a0 + x(a1 +x(a2 + … + x(am-1 + am x))) …) — этот ряд можно привести к ряду полиномов Чебышева, начиная от внутренних скобок, в виде

am-1 + am x = am-1 T0 + am T1

Можно умножить n скобочное гнездо:

a0T0 + a1T1 + … +anTn

на x и добавить к нему следующий коэффициент степени nm-n-1, чтобы получить (n+1) гнездо.

Тогда применяя xT0 = T1; xTn = (Tn+1 + Tn-1)/2 приводим степенной ряд в n скобках, осуществляя преобразование в (n+1) степенной ряд полиномов Чебышева следующим образом:

Например:

fN(x) =

f0 = a0 a0 T0

f1 = a0 + a1 x a0 T0 + a1 T1

f2 = a0 + a1 x + a2 x2 (a0 + )T0 + a1 T1 + ()T2

f3 = a0 + a1 x + a2 x2+a3 x3 (a0 + )T0 +( a1+)T1 + ()T2+()T2

f4 = a0 + a1 x + a2 x2+a3 x3 + a4 x4 (a0 + + )T0 +(a1+)T1a1+

f4 = a0 + a1 x + a2 x2+a3 x3 + a4 x4 +a5 x5 (a0 + + )T0 +( a1++)T1+

+()T2+ ()T3+()T4+()T5

и т. д.

То есть можно вместо

f(x) = a0 + a1 x + a2 x2 +…+am xm

брать ряд f(x) = b0 + b1 T1 + b2 T2 +…+bm Tm

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

Пример:

y = ln(1+x) x - (1)

y T1 – () + ()

y - (2)

Отбрасывая в (1) последний член, получаем погрешность (), равную 0,333 при x = 1.

А в ряд (2) при отбрасывании последних двух членов:

= -00,1666… (так как Tn1)

Таким образом, можно написать

y = ln(1+x) - , обеспечивающее лучшую точность, чем (1).

Теперь, используя определение полиномов Чебышева можно написать:

y = ln(1+x) — это и есть экономизация.

Численная оценка полиномов Чебышева

Tn(x) = 2xTn-1(x) – Tn-2(x)

T0 = 1; T = x

y = ln(1+x) - (3)

Можно оценить (3) первой оценкой численного значения для 4 полиномов Чебышева: (пусть x = 0.3)

T0 = 1; T = 0.3

T2 = (2)(0.3)T1 – T0 = 2·0.3·0.3-1 = -0.82

T3 = (2)(0.3)T2 – T1 = -2·0.3·0.82 – 0.3 = 0.792

y = ln(1.3)

y = ln(1.3) = 0.

Экономизируем разложение ряда Маклорена:

ex = 1 + x +

1 = T0

x = T1

x 2=

x 3=

x 4=

x 5=

x 6=

e x= +…

e x= 1.2661T0 + 1.1302T1 + 0.2715T2 + 0.0443T3 + …

e x= 1.2661 + 1.1302x + 0.2715(2x+ 0.0444(4x 3– 3x) + …

e x 0.9946 + 0.9974x + 0.5430x2 + 0.1771x3 + …

Sin x = x -

Sin x = T1 -

Sin x =

x5 изменяет коэффициент T1< на 1%, x7 - <0.01%

Sin x =

T1 = x; T3 = 4x3 – 3x;

Sin x = 0.9974x – 0.1562x 3= x(0.9974 – 0.1562x2)