Некоторые подходы к решению частичной проблемы собственных значений.
С
пектрм
атрицы–набореёсобственны
хзначений.
A.
Теорем
а1.
Д
оказат
ельст
во:
Axx
x Ax A.
Теорем
а2. Д
лялю
бойвещ
ественнойм
атрицыАкаж
доесобственноезначение
леж
итпокрайнейм
ереводномизкругов
n
ii
ij , i
1,n ком
плекснойплоскости(для ).
j
i
n
x(ii )xi
ijxj i
1,n
Д
оказат
ельст
во: Ax
j
i
n
ii
xi
1,n
ij xi i
j
i
n
n
xj
1
1
ij
ij i
1,n
i
1,n ii
x
x1 max
xi
j
i
j
i
1
xj
x1
1
Оценка спектра матриц.
Т еорем а 3. Д ля м атрицы
к р у г е min
P , Q , г д е
A n n л ю б о е с о б с т в е н н о е з н а ч е н и е
P max
n
i 1 , n
n
ik
k 1
, Q max
j 1 , n
У т в . Е с л и Re i Im - к о м п л е к с н о е ч и с л о ; F i
оценки
j i
min (Im ii F i ) Im max (Im ii F i )
i 1 , n
n
У т в . Е с л и ii F i ij i 1 , n , т о min
i 1 , n
ii
j i
У т в. Д л я эр м и то в о й м атр и ц ы A A* A
2
Fi .
n
i 1
2
n
j 1
ij
kj
ij
, то справедливы
n
i 1 , n
i 1 , n
k 1
min (Re ii F i ) Re max (Re ii F i )
i 1 , n
находится в
.
Итерационный метод вычисления спектрального радиуса.
Примем для простоты что есть полная система собственных векторов Ae i i ei , ( e i , e j ) i ,
то есть система нормированная, 1 2 3 ... m
В базисе e i x
m
(0)
c i e i [ обозначение (…,…) есть скалярное произведение векторов]
i 1
Рассмотрим итерационный процесс x
( k 1 )
Ax
(k )
: x
(k )
k
x ( k ) c1 1 e1 O 2
2
( x ( k ) , x ( k ) ) c1 1
2
k
2k
( x ( k 1) , x ( k ) ) 1 c1 1
k
O 1 2
2k
k
k
O 1 2
k
m
k
c i A e i c i i e i (k –степень)
i 1
1
1 1 O 2 2
1
c1
i 1
k
2
O
1
1
1 k
2
1 O 2
1
c1
k
x A x
определено e 1 с точностью до c 1 (произвольной
2
постоянной). Здесь скорость сходимости определяется .
1
(k )
k
Так как x i
(0)
(k )
k
c1 1 e1 O 2
1
k
( x ( k 1) , x ( k ) )
( x (k ) , x (k ) )
m
x (k )
растут, то необходима нормировка: x ( k )
~x ( k )
k
(k )
1
Решение нелинейных уравнений. Поиск действительных корней.
Решаем уравнения вида f(x)=0
Важно найти все корни => Три задачи: ~ определить число корней;
~ провести отделение корней;
~ вычислить корни с заданной точностью.
Существует ряд правил для определения числа корней и отделения корней.
1. Если на концах некоторого отрезка f(x) разных знаков и непрерывная, то на этом
отрезке есть хотя бы один корень(нечетное количество корней). Если знак f’(x) не
меняется, то корень единственный.
Если f(x) на концах отрезка одного знака, то между концами отрезка нет корней или
их чётное число.
2. Число и положение корней можно определить графически.
3. Корни алгебраических уравнений.
x k - кратный корень
, если
a0 x n a1 x n 1 ... an 1 x an 0 f ( x)
f ( x ) g ( x)( x ~
x )k
Теорема: f(x) с комплексными коэффициентами имеет ровно n комплексных корней с
учетом кратности.
Теорема:
an
a
Все корни f ( x) 0 расположены в кольце
; , где
a ' an a0
a max a1 ,..., an , a ' max a0 ,..., an 1
Правило знаков Декарта(1637г.):
Число положительных корней уравнения f(x)=0 не больше числа перемен знака
в последовательности коэффициентов или меньше на чётное число.
Если корни действительны, то число положительных корней равно числу перемен знака.
Замена (х) на (-х) позволяет оценить число отрицательных корней. (Получить самостоятельно.)
Теорема Штурма (о числе действительных корней уравнения с действительными
коэффициентами), 1829г.:
Системой (рядом) Штурма называется последовательность полиномов с действительными
коэффициентами f0(x),…,fm(x), для которой: - cоседние многочлены не имеют общих корней;
- fm(x) не имеет действительных корней;
- если fi(α)=0, i=1,…,m-1, то fi-1(α) fi+1(α<0);
- если f(α)=0, то f(x)fi(x) меняет знак с «-» на «+», когда x, возрастая, проходит через точку α.
П рим ер систем ы Ш турм а:
f 0 f , f 1 f ,
f m const
f i 1 : f i 1 S f i ( f i 1 ),
С т е п е н ь f i+ 1 м е н ь ш е f i
FN (x)
S
fn (x)
N n
о с т а т о к о т д е л е н и я f i-1 / f i
rp (x)
fn(x)
p n N
остаток от деления
П р и м е р ( М .Я . В ы г о д с к и й « С п р а в о ч н и к п о э л е м е н т а р н о й
м атем атике»)
f a 4 a 3 a 2 a 1 f0
f 4 a 3 3a 2 2 a 1 f1
a4 a3 a2 a 1
3
1
1
a4 a3 a2 a
4
2
4
f2 :
f0
f1
4 a 3 3a 2 2 a 1
1
1
a
4
16
S
1 3
1
3
a a2 a 1
4
2
4
1 3
3 2
1
1
a
a a
4
16
8
16
5 2
5
15
a a
16
8
16
f i 1
Если действительно числа aразности [q(a)-q(b)], где q(y) - число перемен знаков в любой системе Штурма при x=y; значения,
равные нулю, не учитываются. Пользуясь этой теоремой, можно разбить числовую прямую на
промежутки, в каждом из которых есть лишь один действительный корень.
Теорема Бюдана(1822)-Фурье(1820)
(оценка сверху числа действительных корней полинома с действительными коэффициентами):
Число корней полинома в интервале (a;b) равно или на чётное число меньше, чем (t1-t2),
где t1 - число перемен знака в ряду fn(a),f'n(a),…,fn(n)(a), а t2 - в ряду fn(b),f'n(b),…,fn(n)(b).
Каждый кратный корень считается за k корней.
Как правило, все методы поиска корней для класса непрерывных функций –
- итерационные.
Для поиска корня одного уравнения самый простой метод –
- метод половинного деления (дихотомия).
Метод всегда сходится, если корень существует.
Скорость сходимости:
x (k ) x*
b a
2k
Метод Ньютона, метод секущих – частные случаи метода итераций.
x
Метод простой итерации:
(i+ 1 )
= φ ( x (i))
о т в ы б о р а φ (x ) за в и с и т с х о д и м о с т ь и т е р а ц и о н н о г о м е т о д а . Д е й с т в и т е л ь н о :
(i+ 1 )
x
- x * = φ ( x (i)) - φ ( x * ) = φ ’ ( ξ ) ( x (i)- x * ) ( п о т е о р е м е « о с р е д н е м » ) ,
x
(k )
,x
*
, x * - р е ш е н и е
|φ ’ ( ξ ) |< 1 - у с л о в и е с х о д и м о с т и м е т о д а ( |φ ’ ( ξ ) | - с к о р о с т ь с х о д и м о с т и ) .
В аж ное свойство итераций – погреш ность округлений не накапливается
Е с л и д л я н а ч а л ь н о г о п р и б л и ж е н и я '( x
(0 )
) 1 , то м ето д п р о сто й и тер ац и и м о ж ет р асх о д и ться,
поэтом у водится норм ирую щ ая ф ункция: x x (x) f (x)
П р и м ер:
x
2
a
x x x
a
x
x
x
a
a
( x ) '( x ) 2 = > м о ж е т б ы т ь р а с х о ж д е н и е п р и x
x
x
1
a
1
a
x '( x )
2
x
2 2 x
y=x
y=(x)
0<’(x)<1
односторонняя
сходимость
2
– сходится
y=(x)
y=x
-1<’(x)<0
двухсторонняя
сходимость
2
a
x ( k 1) x * x ( k ) x *
Для итераций верно неравенство
const – линейная сходимость
(сходимость со скоростью геометрической прогрессии)
(k ) 0
– сверхлинейная сходимость
Определение: если
то итерация
( l 1)
( x * ) 0
x ( k 1) ( x k )
l 1, p 1
( p ) ( x * ) 0
имеет порядок сходимости р.
( p)
( p) ( x* )
( )
* p
( x ) x ( x x )
... ( x x )
p!
p!
*
(k )
* p
*
(x ) x x
( p)
max ( )
p!
( k 1)
*
x ( x
(k )
( p ) ( )
x )
p!
*
p
x* , x (k )
- характеризует скорость сходимости
Т е о р е м а : е с л и φ ( x ) – н е п р е р ы в н а , д л я л ю б о г о k x (k ) [ a ,b ] и { x (k )} x * , т о x * - к о р е н ь
у р а в н е н и я f(x )= 0 , с о о т в е т с т у ю щ е г о и т е р а ц и о н н о м у п р о ц е с с у x = φ (x ).
Д о к а з а т е л ь с т в о : д л я л ю б о г о k x (k ) [ a ,b ] , с л е д о в а т е л ь н о
a x
(k )
b li m
a lim
x
k
В с и л у н е п р е р ы в н о с т и : lim
x
(k )
(k 1)
li m b a x * b
lim ( x
(k )
) (lim
x
(k )
) x * ( x * ) - к о р е н ь .
Метод секущих (хорд):
f ( x) 0 x x
x b
f ( x)
f ( x) f (b)
f ( x ( 0) ) f (b) 0
x
( k 1)
x
(k )
x(k ) b
(k )
f
(
x
)
(k )
f ( x ) f (b)
x(0)
Уравнение прямой:
b
0
f ( x 0 ) f (b)
0
0 f ( x ) f (b)
y
x f (x ) x
x0 b
x0 b
f(x(0))
f(b)
Оценка погрешности:
x ( k ) x*
max f ' ( x) min f ' ( x)
min f ' ( x )
x ( k ) x ( k 1)
имеем итерационный метод
1-го порядка.
Метод Ньютона (касательных).
f ( x) 0; f ( x) - непрерывная. Существует f ' ( x ); f ' ( x) 0
Можно записать такой итерационный процесс
(k )
f
(
x
)
(k )
x ( k 1) x ( k )
(
x
) /* x x ( x) f ( x) * /
(k )
f '(x )
f ' ' ( x)
*
имеем итерационный метод
' ( x) f ( x)
'
(
x
)
0
2-го порядка.
[ f ' ( x)]2
По формуле Тейлора в окрестности точки
*
h x x
*
( 0)
h x x
: f (x
( 0)
h2
h) f ( x ) hf ' ( x )
f ' ' (0)
2!
(0)
f ( x ( 0) )
f ( x ) 0 f ( x ) hf ' ( x ) h
f ' ( x (0) )
(0)
x* x (1)
x
(0)
*
( 0)
( 0)
f ( x (0) )
f ( x ) 0 f ( x ) hf ' ( x ) h
f ' ( x (0) )
*
(0)
f
(
x
)
x ( 0)
f ' ( x ( 0) )
(0)
( 0)
- линеаризация уравнения f(x)
(0)
Теорема (о сходимости метода Ньютона, основного метода Ньютона):
f ( x) 0, x ( 0) - начальное приближение; выполнены условия :
1
1) f ' ( x ( 0 ) ) 0
B
'
f0
2)
f0
f 0'
3)x : x x ( 0 )
f ' ' ( x ) k
4) B K h
1
2
1 1 2 B K то
1 1 2h
Если
,
x* : x* x ( 0) x ( k ) x* и
h
B K
x ( k ) x* t * t ( k ) , где
t ( k ) - последовательность приблежения метода Ньютона для
k
1
f (t ) t 2 t 0, t * - min корень 0, t (0) 0
2
B
B
2
Утверждение (о сходимости метода Ньютона для at bt c 0 ):
b 4ac 0 t
2
(k)
t , если t
*
Графическое доказательство:
f (t )
b
*
2a t ( 0 ) t
t (1)
t ( 2)
t
0
k
: t
(0)
b
2a
Доказательство
теоремы:
f (t )
1 4
1
K
0
2
2
2 B B (1 2h)
B
1
1 2h
2
1
B
B
t
(1 1 2h ) 0
K
BK
1 1 2h 1 1 2 h
t ( 0 ) 0 t ( k ) min t *
BK
h
2
b
b
4ac ( 0 )
x
t t (k ) t
2a
1 1 2h
1
2
1 1 2h
1
h 0
2
2
h
h
1 1 2h
Доказательство теоремы(продолжение):
Докажем
fk
x ( k 1) x ( k ) t ( k 1) t ( k ) k . Надо оценить f k и f k' !
'
fk
k 0 : x (1) x ( 0 )
f0
1 1 2h
(1)
(1)
(0)
t
t
t
(нн вышли из круга )
'
f0
h
1 (1) ( 0 ) / B
, t t
)
1/ B
Пусть неравенств о верно для (k - 1), покажем верность для (k) :
( f ' (t ) kt
x ( 0 ) x ( k ) x ( 0 ) x (1) x (1) x ( 2 ) ... x ( k 1) x ( k ) t1 (t 2 t1 ) ...(t k t k 1 )
1 1 2h
x ( k ) (нн выходит из круга )
h
f ( x ( k ) ) f ( x ( k ) ) f ( x ( k 1) ) f k' 1 ( x ( k ) x ( k 1) )
t k
/ * f k' 1 x(k) f k' 1 x(k 1 )-f k 1 0 f k 1 f k' 1(x(k)-x(k-1 ) ) * /
Доказательство теоремы(продолжение):
f k f k 1 ( x ( k ) x ( k 1) ) f k' 1 k 1
x( k )
(k )
f
'
'
(
x
)(
x
x)dx (интегральная форма R -1 )(нн выходит из круга )
x ( k 1)
x x ( k 1) t ( x ( k ) x ( k 1) )( x ( k ) x ( k 1) )(1 t )( x ( k ) x ( k 1) )dt
1
f k f ' ' ( x ( k 1) t ( x ( k ) x ( k 1) ))( x ( k ) x ( k 1) )(1 t )( x ( k ) x ( k 1) )dt
0
( f ' ' k - по условию ттеоремы
f k K x
(k )
x
( k 1) 2
1
1 (k )
( k 1)
(
1
t
)
dt
x
x
2
0
Для квадратного уравнения f(t) :
t(k )
(k )
f (t )
t
f ' ' (t )(t
( k 1)
(k )
k ( k ) ( k 1) 2
k ( k )2 t ( k )
(k )
t )dt (t t
) f k f (t ) t
- оценка для f k
2
2
B B
Получим оценку для f k' :
x( k )
f k' f 0' f ' ' ( x)dx f k' f 0' k x ( 0 ) x ( k ) kt ( k ) (ссмвыше)
x( 0)
1
f k' (ии свойств модуля) f k' f k' f 0' (ии условия ттеоремы kt ( k )
B
f ' (t ( k ) ) - прямая квадратного уравнения
x
( k 1)
x
t t
(k )
fk
f (t ( k ) )
'
t ( k 1) t ( k )
(k )
fk
f ' (t )
x ( k ) x* - корень и принадлежит кругу (ии ттеоре анализа о пределах)
Оценка ошибки :
(k )
*
x ( k p ) x ( k ) x ( k p ) x ( k p 1) ... x ( k 1) x ( k ) t ( k p ) t ( k ) p x ( k ) x (*) t * t ( k )
