Б.П. Демидович, И.А. Марон - Основы вычислительной математики (1132358), страница 52
Текст из файла (страница 52)
Если характеристическое уравнение ф(к)=О имеет кратные корни, то их можно рассматривать как мределы несовпадающих корней при бесконечно малых возмущениях коэффициентов уравнения 111. В результате теорема обобщается и на этот случай. й 3. Необходимые и достаточные условия сходимости процесса ятерации для системы линейных уравнений Используя собственные значения матрицы сс = ~а1т), можно дать необходимые и достаточные условия сходимости процесса итерации для линейной системы х = схк+)), (1) где ()=; и х= Те о рема.
Для сходимости процесса итерации х'"'=-ах'ь "+(Ъ (й=1, 2...,) (2) были по модулю меньше единицы. Лак азательство. Из формулы (2) получаем: х'ь' = (Е+ сс+ сс'+... + аь ') р + аьх'ь'. Отсюда следует, что сходимость процесса итерации (2) при произвольных () и х'ел эквивалентна сходимости матричной геометрической прогрессии Ф Е+а+а'+... = ~~а аь. (4) ь=е при любом выборе начального вектора х'ь' и любом свободном члене 1) необходимо и достаточно, чтобы собственные значения матрицы сс, т. е. корни характеристического уравнения де1 (сс — Щ = О, в 31 неовходнныв н лостлточныв головня сходнмостн 391 В силу теоремы 2 из $1 геометрическая прогрессия (4) сходится, если все собственные значения )у(/=1, 2,, л) матрицы сс удовлетворяют неравенствам ~Х;) (1 (/=1, 2,, л). (5) Так как при этом а — О прн Ь - со, то из формулы (3) вы~екает, по процесс итерации сходится прн любых (1 и хю', т.
е. существует 1пп х'ь'=х, где х —, очевидно, решение системы (1). Если неравенства (5) не выполнены, то ряд (4) расходится. В таком случае при некотором выборе начального вектора х'е' процесс итерации, очевидно, также расхолнтся. Таким образом, для сходимости процесса итерации (2) необхолимо и достаточно, чтобы все корни )ы л, ..., 3„ характеристического уравнения ать — Х атв ... ест„ аят а„— Х ... сс,„ =О а„т а„, ... а„„вЂ” )с удовлетворяли условиям: ) Ху! (1 (/=1, 2, ..., л). Следствие. Для сходимости процесса итерации (2) достаточно, чтобы ((сс(((1, (б) какова бы ни была каноническая норма (ср. гл. !Х, $1).
Действительно, в силу теоремы 3 из $ 1, на основании неравенства (6) получаем неравенства (5). 3 а м е ч а н и е. Рассмотрим линейную систему (7) А.к =Ь, тле А= ~а;.) и Ь=(Ь, ... Ь„) — вектор-столбец. Пусть О= л" "' ~О Для приведения системы (7) к специальному аиду (1) обычно полагают: А = с) + (А — Р). Отсюда Е)х = Ь вЂ” (А — 7.)) х, х =Р Ча+Р ' (Р— А) л. Можно принять сг=Р т(Р— А). Таким образом, для сходимости обычного процесса итерации для линейной системы (7) при любом свободном члене Ь и любом начальном векторе л'а' необходимо и достаточно, чтобы все корни Л„ Л„ ..., Х„ характеристического уравнения де([Р ' (Р— А) — ЛЕ[ = О (8) были по модулю меньше единицы.
Пользуясь теоремой об опреде- лителе произведения двух матриц, уравнение (8) можно преобра- зовать следующим образом: де1Р 'бе1[(Р— А) — ЛР[=О бе1 [ЛР+ (А — Р)[ = О, или т. е. ! амЛ аы ... ага аы аыЛ ... ага О а„, а„, ... а„„Л ф 4. Необходимые и достаточные условия сходнмости процесса Зейделя для системы линейных уравнений Для линейной системы х=гкх+[3, , рассмотрим процесс Зейделя ()а где а=[и;7[ и [)= пл чп (ь> Х; " = ~ СГ о.
Иг + /=г ~чр ~агух(~ м+ р,. (1 = 1, 2,, л; л = 1, 2,, ) 1=! при произвольном начальном векторе ю к ( л(0! к1Ю а 392 пополнит. свидания о сходимости итеглционных пгоцвссов (гл. тз и так как бе1Р=аыа„... а„„Ф-О, то О 41 неовходимые и достлточныв тсловия сходимости 393 Положим сс= В+ С, где а„ О ... О О - , О и, ... н,„ ач аьь. ию 10 О О ,. аьь Тогда процесс Зейделя в матричном виде можно записать следующим образом: х'ь' = Вх'ь'+ Сх'ь ы+() (й = 1, 2 (2) Т е о р е м а.
Для сходимости процесса Зедделя (2) для системы (1) ри любом выборе свободного члена () и начального вектора х'ь' необходимо и достаточно, чтобьч все корни Хы ..., Х„ уравнения аы — Х а„... а,„ бе1(С вЂ” (Š— В) Х] = — " " "' '" =О (3) а„,Х «„,ь ... 脄— Л баяли ло модула меньше единицы. Доказательство. Из формулы (2) вытекает: (Š— В) х'ь'=Сх'" "+(). (4) Матрица Š† †неособе, так как бе1(Š— В) = 1. Поэтому равенство (4) можно записать в виде х'"'=(Š— В) 'Схж "+(Š— В) г(). Отсюда ясно, что процесс Зейделя эквивалентен процессу простой итерации, примененному к линейной системе х= (Š— В) ' Сх+(Š— В) 'Д. В силу теоремы предыдущего параграфа, для сходимости итерационного процесса (5) необходимо и достаточно, чтобы корни ..
„ Х„ характеристического уравнения бе(1(Š— В) 'С вЂ” ХЕ) =О (3) удовлетворяли условиям (Хт! < 1 (/=1, 2,, л). Уравнение (6), очевидно, равносильно уравнению (3). Ах =б. (7) Положим вм О ... О О аы ... О о о ФО Для применения метода Зейделя систему (7) обычно записывают в форме Рх = (Р— А) х+ Ь нли х =Р ' (Р— А) х+Р 'Ь. А — Р=В -(-С„ (8) Положим где о...оо1 ал1 ант ал, л-1 О О и ° ° 1 н-г 1н О О ... а, „ , и,„ Тогда Р '(Р— А)=В+С, где В= — Р'В, и С= — Р'С,, причем треугольные ма~рицы В и С реализуют разбиение матрицы системы (8), необходимое для применения процесса Зейделя. На основании фориулы (3) сходимость процесса Зейделя для системы (7) зависит от свойств корней уравнения бе([ — Р 'С вЂ” (Е+Р гВ ) )г) =О.
(9) Уравнение (9) можно заменить эквивалентным уравнением бет((Р+В,) 1+ С ) = О или аыь аи ° ° ° лгн ат1Х итти ... ан алг)~ она)~ алп~ () 0) 394 дополнит. сввдвния о оходимости итягьционных пвоцессов (гл. хг Замечание. Пусть ф 51 сходимость пеоцвссл зайпала для нотмхльной системы 395 Таким образом, для сходнмости процесса Зейделя для системы (1) пря любом свободном члене Ь и любом начальном приближении х'ь' необходимо я достаточно, чтобы все корни к уравнения (10) удовлетворяли условиям (й (~1 У=1, 2, й 5. Сходимость процесса Зейделя для нормальной системы Теорема.
Длл нормальной системы обычный процесс Зейделл сходится при любом выборе начального вектора. Д о к а з а т е л ь с т в о. Пусть линейная система — нормальная, т. е. матрица А= [а;Л вЂ” симметрическая и положительно определенная. Положим А =,О+ (т+ )т», где ам О ... О О а„... О~ ΠΠ†диагональн матрица, — нижняя треугольная матрица, О а„...
атн О О ... атн О О ... Π— верхняя треугольная матрица, являющаяся ввиду симметричности матрицы А транспонированной по отношению к матрице У. Тогда имеем: (О+ (т+ )те) х=Ь. Отсюда Ох = Ь вЂ” ((т+ (т )» и, следовательно, (2) х=О 'Ь вЂ” О '()т+ )") х, где О О ем 1 О О лее ) Согласно предыдущему процесс Зейделя для системы (1) или эквивалентной ей системы (2) строится следующим образом: х'"'=О 'Ь+Вх'и+Схы " (Ь=!, 2, ...), (3) где В= —.О 'У и С= — В 'У . Для сходимости процесса в силу теоремы предыдущего параграфа необходимо и достаточно, чтобы все собственные значения Х матрицы М=(Š— В) 'С были по модулю меньше единицы. В нашем случае имеем: М= — (Е+)) 'У) 1О 'У"= — (й ' (О+УЯ ь0 гУь= = — (О+ У) т 1Ю 'У" = — (О+ У) ' Уь.
Пусть е — единичный собственный вектор матрицы М, соответствую- щий собственному значению Х, т. е. (О+ У) 'Уье= — Хе У"е = — ). (й+ У) е. или Отсюда (У'е, е) = — А [(В+ У) е, е] и, следонательно, (У*е, е) (Ре, е)+(Уе, е) ' Введем обозначения (Ое, е) = ~ а,. ( е, (' =- о > О )=1 (Уе, е) =а+(р (а и () действительны и 1 = ф~ — 1).
396 дополнит. сведения о сходимости итеглционных пгоцвссов [гл. х~ 6 6) спосовы эеевктивной пговввки эсловий сходнмости 397 Ввиду того, что матрипа )гв является транспонированной по отношению к матрице У, получаем: (Уне, е) =(е, Ие) =(Ие, е)в=а — )р. Поэтому (о+а)+ ф и, следовательно, 1' а'+62 1' (о+а)т+ Рт (4) Используя полонгительную определенность матрипы А, будем иметь: (Ае, е) =(Ое, е)+(Ие, е)+(У"е, е) = =о+(а+ф)+(а — 1()) =о+2сс > О, т. е. о+а > — а. (5) Далее, учитывая положительность числа о, очевидно, имеем: о+а > а.
Таким образом, всегда выполнено неравенство о+а > (а!. Отсюда для членов дроби (4) буден иметь: (6) т. е. ))1! <1, что и требовалось доказать. 6 6. Способы эффективной проверки условий сходимости требованию )Хт) <1 (у=1, 2, ..., П) (2) или не удовлетворяют ему. Этот вопрос можно просто разрешить, воспользовавшись известными условиями Гурвица [21.
Для проверки условий теорем сходимости итерационных процессов нужно иметь эффективные критерии, позволяющие определять, удовле. творяют ли корни лы Х„ ..., л„ данного алгебраического полинома У(л) =Р~й +Р~~' + +Р„ (1) 398 дополнит. свндвния о сходимости итхглпионных пгоивссов [гл. х< Теорема Г у рника. Пусть коэффициенты рь(и=0,1, ..., и) полинома (1) действительны, причем Рь) 0 Р~ ~ Ро ) 0 0 ...
0 0 Рь Рь ( Р1 Р, ... 0 0 0 0 0 0 ... Рц Рп-1 Рь-ь О 0 О 0 ... 0 0 Рц — матрица и-го порядка, строки которой представляют собой расширенные последовательности коэффициентов полинома (1) Рьм ю Рхь ю ' ' Ргь-ю где положено р„= 0 при й < 0 и )г ) и. Тогда все корни Х„ Хю ..., Х„полинома (1) имеют отрицательные вещественные части йеХТ<0 (Т'=1, 2„..., п) (т. е, расположены в левой полуплоскости комплексной плоскости Х =а+(р) в том и только том случае, если главные диагональные миноры матрицы М положительны, т. е. л,=р,>о, л =( ~>о (3) л„=р„л„, > о.
П р и и е р 1. Для квадратного трехчлена Рьт~+Рт" +Рз условия Гурвина таковы: р,>о, р,>о, р,>о. Нас интересует вопрос, когда корни полннома (1) удовлетворюот условию (2), т. е. лежат на комплексной плоскости к внутри единичного круга (Х(< 1. С помощью дробно-линейной функции й 61 спосовы эвьяктивной пговвгкн ьсловнй сходнмостн 392 внутренность единичного круга !).~ ( 1 преобразуется в левую полу- плоскость Ке р ( О.
Прн этом наш полнном (1) принимает вид ~(",— '-ц ='~ —,"-")'+'(и)' ' „. ЬЪ (р+ )" +Р (р+ )" ' (р — 1)+ " + р. (р — )"3. Следовательно, корни полннома (1) тогда н только тогда расположены внутри единичного круга, когда вспомогательный полипом г'((х)=~(ра(1+1) +Рг(0+1) (р 1)+.. +Р ((х 1) ) удовлетворяет условиям Гурвица (3), причем знак выбирается так, чтобы старший коэффициент ~(ра+Р + ° +Р ) > О П р и м е р 2. Рассмотрим квадратный трехчлен Р(Х) = Ха+ РХ+~у, (4) где р и л действительны. Вспомогательный полипом имеет вид Р(р) = ~ (((а+1)'+Р ()а+1) (р — 1)+ р (р — 1)Ч = = -ч-1(1+ р+д) ра+ 2 (1 — у) (х+ (1 — р+дЯ.
Из условий Гурвица получаем: 4-(1+р+д) > о, ~(1 — ч) > О ч-(1 — Р+л) > О. Рассмотрим случаи: а) д(1, тогда р> — р — 1 и д>р — 1; б) д> 1, тогда и ч. — р — 1 и д < р — 1, что невозможно. Следовательно, уравнение (4) имеет корни Хы Хя, по модулю меньшие единицы, тогда и только тогда, когда (1+ч, (ч!(1 (5) Так как при л = 2 характеристическое уравнение матрицы сь имеет вид — ~=о или Р— (аы + сс„) Х + бе1 сг = О, то для сходнмостн соответствующего процесса итерации для системы двух уравнений необходимо, чтобы )де1сг(<1. (и ю 400 дополнит. свидания о сходимости итяглцнонных пгоцвссов (гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
