Численные методы. Корнюшин П.Н. - 32 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

Составители: 

Рубрика: 

32
....)22()2(
242
4031
2
2
22
20
2
1
22
0
n
nnn
axaaaaaxaaaxa +++−++−+
−−
Сделаем замену переменной x=-x
2
:
....)22()1()2()1()1(
22
4031
2
2
21
20
2
1
12
0 n
nnnnnn
axaaaaaxaaaxa +++−−+−−−−
−−−−
Домножим получившееся выражение на (-1)
n
:
...)22()2(
2
4031
2
2
1
20
2
1
2
0
++−+−+
−− nnn
xaaaaaxaaaxa
Правило получения коэффициентов после квадрирования: коэффициент b
k
при x
n-k
равен
...22
2211
2
++−=
+−+− kkkkkk
aaaaab до тех пор, пока не будет достигнут коэффициент
2
0
a или
.
2
n
a
Процесс квадрирования можно повторить сколь угодно раз. Каков же критерий останова?
Пусть многочлены
,...
1
10 n
nn
bxbxb +++
−
(23)
n
nn
cxcxc +++
−
...
1
10
(24)
являются результатами квадрирования, т.е. (24) получается из (23) в результате очередного
квадрирования. Пусть корни многочлена (23) уже настолько по модулю отличаются друг от друга,
что можно применить (18), т.е.
.
1
)1(
−
−≈
i
i
i
b
b
x
Тогда корни
}
{
)2(
i
x многочлена (24) тем более могут быть получены с применением (18),
т.е.
.
1
)2(
−
−≈
i
i
i
c
c
x
Поскольку
,,...,2,1,)(
2)1()2(
nixx
ii
=−= то .//
2
1
2
1 −−
≈
iiii
bbcc Итак, с учетом того, что
,
2
00
bc = для каждого i получаем:
.
2
ii
bc ≈ (25)
Следовательно последовательность процессов квадрирования следует заканчивать тогда,
когда соотношение (25) выполняется с заданной степенью точности. Между корнями
}
{
i
x
исходного многочлена и корнями
}
{
)(k
i
x многочлена, получающегося после k итераций,
существует простая связь:
.|)(|||
2/1)(
k
k
ii
xx = (26) 
                                                                       32


                    a 02 x 2 n + (− a12 + 2a 0 a 2 ) x 2 n − 2 + (a 22 − 2a1 a 3 + 2a 0 a 4 ) x 2 n − 4 + ... + a n2 .
         Сделаем замену переменной x=-x2:
         a 02 (−1) n x n − (−1) n −1 (a12 − 2a 0 a 2 ) x n −1 + (−1) n − 2 (a 22 − 2a1 a 3 + 2a 0 a 4 ) x n − 2 + ... + a n2 .
         Домножим получившееся выражение на (-1)n:
                           a 02 x n + (a12 − 2a 0 a 2 ) x n −1 + (a 22 − 2a1 a 3 + 2a 0 a 4 ) x n − 2 + ...
         Правило получения коэффициентов после квадрирования: коэффициент bk при xn-k равен
bk = a k2 − 2a k −1 a k +1 + 2a k − 2 a k + 2 + ... до тех пор, пока не будет достигнут коэффициент a 02 или
a n2 .
       Процесс квадрирования можно повторить сколь угодно раз. Каков же критерий останова?
Пусть многочлены
                             b0 x n + b1 x n −1 + ... + bn , (23)
                                           c 0 x n + c1 x n −1 + ... + c n
                                                           (24)
являются результатами квадрирования, т.е. (24) получается из (23) в результате очередного
квадрирования. Пусть корни многочлена (23) уже настолько по модулю отличаются друг от друга,
что можно применить (18), т.е.
                                                                           bi
                                                           x i(1) ≈ −           .
                                                                          bi −1
                           {
         Тогда корни x i( 2 )      } многочлена (24) тем более могут быть получены с применением (18),
т.е.
                                                                               ci
                                                                x i( 2) ≈ −          .
                                                                              c i −1
         Поскольку x i( 2 ) = −( x i(1) ) 2 , i = 1,2,..., n, то c i / c i −1 ≈ bi2 / bi2−1 . Итак, с учетом того, что
c 0 = b02 , для каждого i получаем:
                                                  c i ≈ bi2 .
                                                     (25)
       Следовательно последовательность процессов квадрирования следует заканчивать тогда,
когда соотношение (25) выполняется с заданной степенью точности. Между корнями {x i }
исходного многочлена и корнями                       {x }(k )
                                                         i            многочлена, получающегося после k итераций,
существует простая связь:
                                                                              k
                                                | x i |= (| x i( k ) |) 1 / 2 .          (26)

Страницы