книги / Численные методы. Ч. 1
.pdfОценка погрешности методомРунге1*
С целью получения оценки погрешности рассмотрим формулу интегрирования методом трапеций. Для отрезка [xk_,, хк ] введем обозначения:
= 'jffMdx.
Jh .k= -[f(Xk) + f(*k-,)]-
В соответствии с полученным выражением (7.12) можно записать:
v - = J |
+f(xk.,)]=Vk - ~ |
г к и). |
или иначе, |
|
|
|
Jk- J , k «C kh3 |
(7.14) |
Теперь уменьшим шаг вдвое и вновь проведем интегрирование на том же отрезке [хк_,, хк];в этом случае общая погрешность
(,,я
Вычитая формулу (7.15) из выражения (7.14), получаем
Jh/U - Jhik*C kh -2Ск^—j =Ск .
Отсюда можно определить коэффициент
“jjjH^h/lk “ Jh.k)
иподсчитать погрешности вычисления интегралов:
~” ^h.k)’
I Рунге Карл Давид Тольме [30.8.1856 - 3.1.1927] - немецкий физик и математик. В 1876 - 1877 годах учился в Мюнхенском, в 1878 - 1880 годах - в Берлинском университетах. Работал в Берлине, Ганновере, Геттингене.
Следовательно, зная величины J^ k , Jh k, можно получать оценки погрешностей, получаемых при вычислении интегралов.
В более общем случае (для произвольной схемы интегрирования с порядком погрешности р), можно получить следующие выражения:
Jk ~ J^k * Ckhp,
|
|
|
р |
|
^к ^ь/lk |
|
|
г |
2?h?h |
|
I ^ |
Отсюда, оценки погрешности принимают вид |
|
||
^к |
2*~1 |
(^Ь/U |
Л,к)» |
^h.k * |
_1_
К-*Ы2.к™ 2 ^ - 1 '(^ёОк “ ^Ь.к)*
Приведенные формулы позволяют автоматизировать процесс вычисления интегралов с заданной точностью. Пусть на каждом из отрезков половинное дробление
производится до тех пор, пока не выполнится условие
|Vk| =|jk _ ^h/Lk| * ^р-1 _ | (^h/2.k ~ \k ) ^ ^ _ a * k = l.n.
Тогда общая погрешность интегрирования |
|
||
lJ - |
I = Z K N |
|
Z h = е • |
|
k=l |
О ” a |
k=l |
Таким образом, вычисления с переменным шагом позволяют проводить численное интегрирование с заданной точностью при наименьших затратах.
Квадратурные формулы интерполяционноготипа
Представим функцию f(x) на всем отрезке [а, Ь] полиномом Лагранжа:
L { х ) = £ |
( Х ~ Хо ) - - - { Х ~ Xk-lX х ~ Xk » l } - - { X ~ х в ) |
f(xk). |
|
к=о(Хк Хо)*— *(Х к X k - l K X k Х к*1 )■ *• |
|
||
” Х п ) |
|
Сопоставляя полученное выражение с формулой (7.2), получим явный вид для функций срк(х):
„ , й
(xk - x w)...(xk - х к ,)(хк - х ы )...(хк -х„)
Теперь весовые коэффициенты формулы (7.3) определяются явным образом:
^ |
г / |
г (х —х0) -..(х —хк -)(х —хк*,)... |
(х —х„) |
, |
, — |
|||
С, |
= f<Pk |
x)dx= fr ^ -- |
У - А ----- ---------- |
"О |
V |
ш> |
dx, |
к = 0,п. (7.16) |
{; (хк - х 0)...(хк - х к.,Ххк -Хы )...(хк -х„)
Для подсчета погрешности квадратурной формулы интерполяционного типа воспользуемся полученной ранее оценкой погрешности интерполяционного полинома:
г(* )-М * ) = -^ ; У м( 4 4б[а,Ь], а)(х) = (х -х ,)(х -х ,)-...(х -х „ ).
Погрешность формулы приближенного интегрирования на отрезке [а, Ь]
Ь |
„ |
b |
h f ( n+,) / c ) |
* = }f(x)dx - g € kf(xk) = j[f(x) - L„(x)]dx = j - J ® ( x ) d x ,
Из последнего соотношения очевидно, что квадратурная формула интерполяционного типа выполняется точно для всех функции, являющихся полиномами степени не выше п. В этом случае в формуле (7.3) имеет место точное равенство.
J f(x)dx = |
Ckf(хk). |
a |
k-1 |
Справедливо и обратное утверждение.
Теорема 7.1. Если квадратурная формула Jf(x)dx = ]£ d kf(xk) является точной для |
||
. |
к=0 |
|
многочленов степени п, то она является квадратурной формулой |
||
интерполяционного типа. |
|
|
Доказательство. Покажем, что |
|
|
а.-с.-К[ ■ - ^ 4 - ^ - а - к ) |
k.G. |
|
{ (xk - x„)... (xk - xk ,)(xk - xk„ )... |
(xk - x„) |
|
Пусть функция f(x) является полиномом степени п, тогда ее можно представить
в форме полинома Лагранжа
|
1-0 |
|
|
/ч |
(х -х „ )...(х -х , .Х х -х и1) ...( х - х п) |
. |
---- |
Поскольку все функции Ф,(х), i = 0.n являются |
по |
построению полиномами |
|
степени п. то в соответствии с условием теоремы |
|
|
|
|
j<p1(x)dx = X d k<P1(xk) = X d k5 lk =dj, |
i = 0,n, |
так как согласно правилу построения полинома Лагранжа Ф*(хк) = 6л .
С другой стороны, согласно выражению (7.16)
г |
d v |
г |
(х-х„) |
...(х-х, ,)(х-х, .)... |
(x-xn) |
--- |
|
/ч, |
х ^ х = М |
----- И -а ----- |
^ |
---- ^dx = c ,. |
i = 0,n, |
||
. |
|
,(Х,-Х„)... |
(х,-х,.,Хх|- х ы )... |
(х,-х0) |
|
||
то есть d, = С,, |
i = 0,п, что и требовалось доказать. |
|
|
Квадратурные формулы наивысшей точности. Формулы Гаусса
Зададимся целью построить на заданной сетке П п точную квадратурную формулу вида (7.3) для полинома максимально возможной степени.
Рассмотрим полиномы вида х“, а = 0,ш. Для каждого такого полинома запишем
точную квадратурную формулу интерполяционного типа:
Jxadx = ]TCkx“. |
a = 0,m. |
(7.17) |
|||
. |
kMi |
|
|
|
|
В компонентной записи (после интегрирования): |
|
||||
|
a = 0, Ь -а = ]ГСк ; |
|
|||
|
, |
Ь’ - а 1 |
^ |
|
|
|
a = 1 - |
— |
L |
^ Z c kxk; |
|
|
|
|
k=o |
|
|
|
а = 2. |
^ |
3 |
= ± с л ; |
|
|
|
|
k=« |
|
|
|
|
b4 - Я4 |
n |
|
|
|
а = 3- V - = I C kx l; |
|
|||
|
а = ш, |
bm+l - a m+l |
m |
||
|
m + 1 |
= Z c kxk |
|||
|
|
k=0 |
|
Выражения (7.17) можно рассматривать как систему (m+1) нелинейного алгебраического уравнения относительно (2п+2) неизвестных,
С0,С р С2, ..., Сп, х0, хр х2, ..., хп.
Для разрешимости этой системы уравнений потребуем, чтобы число уравнений
было равно числу неизвестных, то есть ш+1=2п+2, откуда следует, что ш=2п+1.
Иными словами, задача заключается в выборе сетки Пп, содержащей (п+1) узлов,
обеспечивающей точность формулы (7.3) для полиномов степени (2п+1).
Пример |
7.1. |
Пусть |
а |
= |
-I, |
b = 1; |
рассматривается разностная сетка Ц , |
содержащая |
два |
узла: |
Хо |
и |
Х|. |
Требуется |
определить положения этих узлов м |
коэффициенты С0, С, для полинома степени ш = 2n + I = 3.
Система уравнений (7.17) для рассматриваемого случая принимает вид
- =С0 +С,; 0 = Сох0+С,х,;
~ = С0хп +С,х,;
0 = C„xJ +C,xJ.
Из второго уравнения |
0 = (2-С ,)х0+С,х|; *0 = |
С,*, . |
|||
С ,- 2 ’ |
|||||
|
|
|
|
||
Из последнего уравнения |
0 = (2 —С,) |
с М |
|
|
|
|
|
(С ,-2)3 |
|
||
Отсюда, при условии, что х, *0, получаем |
|
|
|||
C,J = (C ,-2 )J |
С, = ± (С ,-2 ), |
С, = 2—С ,, С ,=1. |
|||
Соответственно, |
|
|
|
|
|
С, = 2-С , = 1; |
х0 |
- ^ i - = -Xr |
|||
|
|
|
С ,- 2 |
1 |
Из оставшегося уравнения
- = С„х" + С,х? = 2xf
Отсюда вытекает, что
Jf(x)dx=f(x„) + f(xl) =
I
Эта формула точна для любого полинома третьей степени.
Теорема 7.2. Квадратурная формула (7.3) является точной для любого многочлена
степени m=2n+l тогда и только тогда, когда выполнены условия: |
|
1. Многочлен |
|
0)(х) = (х - х „ )(х - х ,) - ...(х - х п) |
|
ортогонален любому многочлену q(x) степени не выше п, то есть |
|
ь |
|
Ja>(x)q(x)dx = 0. |
(7.18) |
2. Формула (7.3) является квадратурной формулой интерполяционного типа,
ьрччем коэффициенты Ск. к О.п определяются согласно (7.16).
Доказательство. Докажем необходимость условия теоремы.
Пусть формула (7.3) точна для любого полинома степени ш=2п+1. Это означает, что она точна и для произведения to(x)q(x), имеющего степень не выше 2п+1, то есть
ьп
J<o(x)q(x)dx = £ C k<B(xk)q(xk) = 0.
a k=0
так как ©(xk) = 0 Vxk е£2п по построению функции ш(х).
Формула (7.16) справедлива в силу выполнения условий предыдущей теоремы 7.1. Докажем достаточность условии теоремы. Пусть выполнены требования 1 и 2;
f(x) - многочлен степени (2п+1). Представим f(x) в виде:
f(x) = a(x)q(x)+r(x),
причем q(x) и г(х) имеют степени не выше п.
Конструктивно такое разложение можно получить следующим образом. Для простоты положим п=1 (два узла), тогда ш=3. Пусть
f(x) = а + bx + сх: +dx3
- полином степени ш=3; ш(х) = (х - х 0)(х -х 1).
Пусть
q(x) = а + Рх, г(х) = у + 5х
- функции с коэффициентами а,р ,у ,5 , подлежащими определению. В этом случае
<о(x)q(x) + г(х) = Рх5 + (о -р (х 0 +х,))х! +(рх0х, - а(х„ +х,) + б)х +(ах0х, + у).
Из условия <o(x)q(x) + г(х) = f(x) получаем систему алгебраических уравнений
P=d;
a -P (x 0+xk) = c;
Px0x0-a (x 0+x0) +5 = b; ах0х„+у =
относительно искомых коэффициентов a,p,y,6 .
h |
b |
b |
ь |
Jf(x)dx = J©(x)q(x)dx + Jr(x)dx = Jr(x)dx.
a |
a |
a |
a |
Поскольку (7.3) является формулой интерполяционного типа, то она точна для полинома г(х). имеющего степень не выше п. Отсюда получаем
| r(x)dx = £ C kr(xk) = Z C k(f(xk)-ffl(xk)q(xk) ) = £ C kf(xk) .
J |
k-0 |
k=0 |
k=0 |
В последнем соотношении вновь учтено, что <o(xk) = 0, Vxk бП„.
Из двух последних выражений следует,
Jf(x)dx = £ C kf(xk),
ак=0
то есть формула (7.3) оказывается точной для любого многочлена степени (2п+1), что и требовалось доказать.
Использование в условии ортогональности (7.18) в качестве q(x) системы
полиномов а = ().п позволяет рассматривать это условие как систему
алгебраических уравнений относительно координат узлов разностной сетки хк, к = 0,п, что позволяет упростить построение формул Гаусса:
' ь |
|
|
Jl |
(х - х 0) ... (x-x„)dx = 0: |
|
а |
|
|
Ь |
|
|
, Jx |
(x-x„)-... (x-x„)dx = 0; |
(7.19) |
Ь
|х " (х -х„) „. (x-x„)dx = 0.
ъа
Пример 7.2. Пусть, как и в примере 7.1, а = -1, Ь = 1; рассматривается разностная сетка, состоящая из двух узлов: n = 1. Требуется определить положения узлов разностной сетки для полинома степени m = 2n + 1= 3.
(1
|
Jl-(x-x„Xx-x,)dx =0, |
|
-I |
|
I |
|
fx (x - x 0Xx-x,)dx =0. |
Интегрируем первое уравнение: |
|
| |
1 |
Jl • (х - х„Хх - Х1)<& = /(х 1 - х(х0 + Х|) +x0x,)dx = |
|
X X- , |
. |
у - у ( Х п + Х ,) + ХХ„Х, = -+2хЛх, =0,
Аналогично интегрируем второе уравнение системы:
J x (x -x 0)(x-x))dx= J(x3 - х 2(х0 +x,) +x x 0x,)dx =
х4 х3 / ч х2
— - y l X o + X . j + y X o X ,
х0=-х,.
Совместно решая полученные уравнения, получаем
- 4
что совпадает с результатом примера 7.1.
Рассмотрим условия существования и единственности системы уравнений (7.19). Представим полином
о(х) = (х-х0)-...(х -х 11)
в виде
(o(x) = a„ +а,х +а2х2 +... + xn+l
Условия ортогональности (7.18) |
|
|
|
jx“ (а0 + а,х + а2х2 + ... + xn+1)dx = 0, |
а = 0,п, |
b |
h |
|
Jxu |
(a„+a,x+ a2x2 - ...+anxn)dx = -Jxu |
xn+,dx. a = 0,n |
можно записать в виде системы линейных алгебраических уравнений относительно
коэффициентов а к, к = (),п.
Рассмотрим соответствующую систему однородных уравнений |
|
|
Jxa (а,, + а,х + а 2х2 + ... + aIlxn)dx =0. а = 0,п. |
(7.20) |
|
Домножим каждое из этих однородных уравнений на соответствующее аа и |
||
просуммируем: |
|
|
п ^ |
|
|
£ j a (Ix“ (а0 +а,х + а 2х2 + |
-fanxn)dx = 0. |
|
а=»„ |
|
|
Ь |
п |
|
J(aH+ а,х + а2х2 + ... +anx")^aaxadx = 0, |
|
|
а |
|
|
j ' f11=0i X/ x“] |
dx=0- |
|
Отсюда очевидно, что последнее равенство возможно лишь при условии
= о .
i/ -0
откуда, в силу линейном независимости функций \ и а =0,п . следует
=-- 0, а = 67п .
Это означает, что однородная система (7.20) имеет только тривиальное решена, то есть определитель системы уравнений отличен от нуля. Таким образом. Полином
о>(х)-(х х,,)-... (х -х„)
определяется единственным обр;