Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків

Досліджено умови, які спричиняють сповільнення швидкості збіжності ітераційних методів розв’язування систем Ax=b та умови, що дозволяють прискорити збіжність процесу....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автори:	Абрамчук, В.С., Абрамчук, І.В.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Назва видання:	Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/86468
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків / В.С. Абрамчук, І.В. Абрамчук // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2013. — Вип. 8. — С. 5-22. — Бібліогр.: 16 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-86468
record_format	dspace
spelling	irk-123456789-864682015-09-19T03:01:22Z Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків Абрамчук, В.С. Абрамчук, І.В. Досліджено умови, які спричиняють сповільнення швидкості збіжності ітераційних методів розв’язування систем Ax=b та умови, що дозволяють прискорити збіжність процесу. Both the conditions account for the slowing of convergence rate of iterative methods of Ax = b systems solving and the conditions allowing accelerate the convergence of iteration process are investigated. 2013 Article Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків / В.С. Абрамчук, І.В. Абрамчук // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2013. — Вип. 8. — С. 5-22. — Бібліогр.: 16 назв. — укр. 2308-5878 http://dspace.nbuv.gov.ua/handle/123456789/86468 519.612 uk Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Досліджено умови, які спричиняють сповільнення швидкості збіжності ітераційних методів розв’язування систем Ax=b та умови, що дозволяють прискорити збіжність процесу.
format	Article
author	Абрамчук, В.С. Абрамчук, І.В.
spellingShingle	Абрамчук, В.С. Абрамчук, І.В. Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
author_facet	Абрамчук, В.С. Абрамчук, І.В.
author_sort	Абрамчук, В.С.
title	Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків
title_short	Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків
title_full	Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків
title_fullStr	Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків
title_full_unstemmed	Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків
title_sort	дослідження швидкості збіжності класичних ітераційних методів розв’язування систем ax = b великих порядків
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2013
url	http://dspace.nbuv.gov.ua/handle/123456789/86468
citation_txt	Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків / В.С. Абрамчук, І.В. Абрамчук // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2013. — Вип. 8. — С. 5-22. — Бібліогр.: 16 назв. — укр.
series	Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
work_keys_str_mv	AT abramčukvs doslídžennâšvidkostízbížnostíklasičnihíteracíjnihmetodívrozvâzuvannâsistemaxbvelikihporâdkív AT abramčukív doslídžennâšvidkostízbížnostíklasičnihíteracíjnihmetodívrozvâzuvannâsistemaxbvelikihporâdkív
first_indexed	2025-07-06T13:57:19Z
last_indexed	2025-07-06T13:57:19Z
_version_	1836906174097653760
fulltext	Серія: Фізико-математичні науки. Випуск 8 5 УДК 519.612 В. С. Абрамчук, канд. фіз.-мат. наук, І. В. Абрамчук, старший викладач Вінницький державний педагогічний університет імені М. Коцюбинського, м. Вінниця, *Вінницький національний технічний університет, м. Вінниця ДОСЛІДЖЕННЯ ШВИДКОСТІ ЗБІЖНОСТІ КЛАСИЧНИХ ІТЕРАЦІЙНИХ МЕТОДІВ РОЗВ’ЯЗУВАННЯ СИСТЕМ Ax b  ВЕЛИКИХ ПОРЯДКІВ Досліджено умови, які спричиняють сповільнення швидкості збіжності ітераційних методів розв’язування систем Ax b  та умови, що дозволяють прискорити збіжність процесу. Ключові слова: метод похибок, нев’язок, найшвидшого зменшення нев’язок, найшвидшого спуску, Гауса-Зейделя. Не розв’язані проблеми. Основною проблемою розв’язування систем Ax b  з дійсними квадратними невиродженими матрицями великих порядків 610 — 910 з довільним розташуванням ненульових елементів є побудова ефективних ітераційних методів, що збігаються для всіх  nA M R , rank A n . Другою не розв’язаною проблемою є побудова алгоритмів, що коректують процес збіжності і забезпечують стійкість обчислюваль- ного процесу в умовах похибок заокруглення. Сучасні ітераційні методи будуються на основі узагальнення класичних методів, що широко застосовуються при розв’язуванні різницевих і сіткових рівнянь [5—8; 10—16]. Серед класичних ітераційних методів виділимо метод мінімаль- них похибок, найшвидшого зменшення нев’язки, мінімальних нев’я- зок і найшвидшого спуску [5]. Дослідимо прискорення швидкості збі- жності цих методів, а також методу Гауса-Зейделя при розв’язуванні сіткових рівнянь. Не дивлячись на всебічне вивчення і узагальнення цих методів, недостатньо досліджені умови, що прискорюють їх швидкість збіжності. Нехай лінійний однокроковий ітераційний метод  ( ) ( 1) ( 1) ( 1) k k k k k ku u H Au f G u b            , 1, 2,...k  , (1) є узгодженим для системи Au f  (2) © В. С. Абрамчук, І. В. Абрамчук, 2013 Математичне та комп’ютерне моделювання 6 з дійсною невиродженою матрицею ( )nA M  , де k kG I HA   — матриця переходу методу (1), kb H f   , ( )nH M  — невиродже- на матриця, k  . Для вектора похибок ( ) ( ) k ku u      , * 1u A f  , ітераційний метод (1) набуває вигляду ( ) ( 1) , 1, 2,... k k kG k      (3) Для випадків TH A , k T kG I A A   , 2 2( 1) ( 1) 2 2 k T k k r A r     ; (4) TH A , k T kG I A A   , 2 2( 1) ( 1) 2 2 T k T k k A r AA r     ; (5) H E , 0TA A  , k kG I A   ,  ( 1) ( 1) 2( 1) 2 ,k k k k Ar r Ar         ; (6) H E , 0TA A  , k kG I A   ,   2( 1) 2 ( 1) ( 1), k k k k r Ar r         ; (7) ітераційний процес (1) відповідно називають методом мінімальних по- хибок, найшвидшого зменшення нев’язки, мінімальних нев’язок і найш- видшого спуску (SDM) [5]. Розв’язок * 1u A f  сумісної системи (2) будемо розглядати як елемент евклідового простору nE з скалярним добутком   1 , n j jj u v u v     ,  1,..., n nu u u    ,  1,..., n nv v v    . За матричну норму на  nM  виберемо спектральну норму, за число обумовленості матриці A по відношенню до спектральної норми вибе- ремо число max min( ) ( ) ( )T TA A A A A   . Мета статті: знайти умови, що прискорюють ітераційний про- цес (1)—(3) за умов (4)—(7). Постановка задачі. 1. Встановити умови, які забезпечують опти- мальну (найкращу) швидкість збіжності процесу (1), для методів (4)— (7). Описати області max , min найшвидшої та найповільнішої збіж- ності методів. 2. Обґрунтувати перспективність узагальнення методу Гауса-Зейделя для розв’язування сіткових рівнянь. 3. Визначити оптима- льні параметри, що прискорюють швидкість збіжності методів. 4. Дослі- дити, як впливає число обумовленості матриці cond A та розподіл влас- них значень на швидкість збіжності ітераційних процесів (4)—(7). Серія: Фізико-математичні науки. Випуск 8 7 Дослідження швидкості збіжності методу мінімальних похи- бок. Проаналізуємо процес (1) для випадку оптимізації методу міні- мальних похибок за рахунок вибору послідовності оптимальних па- раметрів k  . Ітераційний процес (4) для знаходження вектора похибки  k  реалізується процедурою  ( ) ( 1)k T k kI A A       , 1,2,...k  . Позначимо через  ( )T i A A множину власних значень матриці TA A , а через { }iv  — повну ортогональну систему власних векторів мат- риці TA A . Нехай вибраний довільний початковий вектор (0) u u   . Позначимо через     1 ,...,span m T m i iH A A v v   — підпростір власних векторів матриці TA A мінімальної розмірності, якому належить вектор (0) (0) u u      . Тоді вектор  0  буде однозначно розкладений у підп- росторі mH : (0) i ii I c v     ,    0ii I c   ,  1,..., mI i i . Лема 1. Для довільних значень параметрів k  вектори по- хибок  k  , 1, 2,...k  , методу (1) належать підпростору mH , якому належить  0  . Доведення. Застосуємо метод математичної індукції. Для 1k  маємо        11 (0) 1 11T i i i i i mi I i I I A A c v c v H                 , де  0 i ic c ,      1 0 11i i ic c    , i I . Допустимо, що  k mH   , 1k  , тоді для вектора      1 1 k kT kI A A       матимемо    11 kk i i mi I c v H      ,      1 11k k i i k ic c     , (8)  T i i A A  , i I . Доведення леми 1 завершено. З формули (4) і леми 1 слідує оптимальний алгоритм збіжності процесу (3), з нестаціонарною матрицею tk T kG I A A  , який забез- печується вибором параметрів k :  1 1 m T i A A    ,   1 2 1 m T i A A     ,…,   1 1 m T i A A    . (9) де 1 2 ... mi i i     , ji I , 1,...,j m . Математичне та комп’ютерне моделювання 8 Підставивши ці значення у формулу розкладу (8) для 1k m  , дістанемо      * 0m m mu u u u           . Висновки. 1. Метод мінімальних похибок збігається при оптималь- ному виборі параметрів i за формулою (9) для довільної невиродженої матриці A за скінчене число кроків в умовах абсолютно точних обчис- лень. Число кроків m залежить від вибору початкового вектора  0u  . 2. Для практичного забезпечення максимально швидкого проце- су збіжності, необхідно щоб елементи послідовності  1 k  наближа- ли власні значення матриці TA A на відрізку 1 , mi i    . 3. Множиною max є об’єднання усіх сингулярних прямих (площин для кратних власних значень), що визначаються власними парами   ,T i iA A   матриці TA A :  :i iS u u u H      ,   1 ,...,span si i iH v v   , j j T i i iA Av v   , [1, ]ij s , i I , ii I s n   . 4. Оптимізація процесу збіжності методу мінімальних похибок здійснюється в околі будь-якої сингулярної прямої (площини), що визначається власною парою   ,TA A   матриці TA A . Порівняємо швидкість збіжності стаціонарного процесу (3) з мат- рицею переходу TG I A A   з оптимальною швидкістю збіжності методу з параметрами послідовності (9). Для збіжності до нуля евклі- дової норми вектора похибки  k  , який задовольняє (1), (3) при k  , необхідно і досить, щоб виконувалась нерівність [14]     max 1 1i i M G      . Оптимальне значення параметра  знаходиться з умови мінімі- зації спектрального радіуса    за формулою [14] * 2 m M    ,   1 1 M m m m M MM m                  , (10) де  0 min T im A A  ,  max T iM A A . Взагалі, межі m , M будуть залежати від початкового вектора  m  : 1i m  , mi M  1 1 1 2 1 m mi i i i          . Порівнюючи оптимальні параметри k з Серія: Фізико-математичні науки. Випуск 8 9 послідовності (9) з  за формулою (10), встановлюємо причину більш повільної збіжності стаціонарного процесу (3), побудованого на основі мінімізації спектрального радіуса матриці TG I A A  . Перейдемо до аналізу методу мінімальних похибок з параметра- ми, визначеними за формулою (4). Лема 2. Для довільних векторів  kx  швидкість збіжності мето- ду мінімальних похибок визначається коефіцієнтом                1 1 12 1 2 2 1 1 1 2 2 , 1 cos , , , . k k kT k k k K A A A K A                      (11) Доведення леми 2. Виконаємо перетворення:              2 1 2 2 1 1 12 22 2 1 2 2 , k k k k kT kT r A r A r                              22 22 11 2 2 21 12 2 22 21 1 2 2 kk k kT k kT T rr A r A r A r                            . Оскільки        2 1 1 1 2 ,k k kTA r r       , то            22 2 2 1 1 1 1 12 2 2 2 cos ,k k k k kT TA A r A r                       , тоді           22 2 2 2 2 1 1 1 1 2 2 2 2 2 1k k k k kTr A r                          , отже       2 2 1 1 1 2 2 ,k k kK A        . Доведення леми завершене. З формули (11) випливає, що метод мінімальних похибок збі- гається найповільніше для тих векторів  1k  , для яких досягає міні- муму функціонал     1 12cos ,k kTA A    [1—4]. Дослідимо, за яких умов швидкість збіжності методу мінімаль- них похибок сповільнюється. Розкладемо вектор нев’язки u x      Математичне та комп’ютерне моделювання 10 в базисі за власними векторами матриці TA A : 1 n i ii c v     , 1 nT i i ii A A c v      , 2 2 2 1 n ii c    , 2 2 2 12 nT i ii A A c     , 2 1iv   , [1: ]i n  (власні значення  T i A A взяті з їх кратностями). Максимальне відхилення за напрямком вектора TA A  від оп- тимального u x      на розв’язок системи A x b  з точки u  вимі- рюється величиною       * * * 2 2 2 2 2 22 , min cos , min cos , min n n n T T T u c c T u x c x c x A A A A A A A A                                  2* 2 2 2 1 1 12 2 2 2 1 1 1 min min n n n i i i i i i n n nc t c x i i i i i i i i c t c c t                                     , 1[ ,..., ]Tnt t t  , 2 0i it c  , де [1: ]i n ,   2 1 , n T i i i A A c       . Складемо функцію Лагранжа [9] 2 2 1 1 ( , ) ( ) n n i i i i i i L t t t g t                   , 1 ( ) 1 0 n i i g t t      , [1: ]i n  : 0it  . Дослідимо ( , )L t   на умовний екстремум: 2 2 2 2 1 1 1 1 2 0 n n n n j i i i i j i i i i j i i i i L t t t t t                                       і або 0 j L t    , або 0jt  [9]. Виконавши перетворення, дістанемо систему лінійних алгебрич- них рівнянь відносно параметрів jt , j I , де I множина індексів [1: ]j n для яких 0 1jt  :  12 0, , 1, 1, i j i i I i i I t j I j t                   Серія: Фізико-математичні науки. Випуск 8 11 де      1 2 ...T T T nA A A A A A     . Для  1 max TA A  ,  min T n A A  , 2 3 1... 0nt t t     , ма- тимемо систему рівнянь 1 1 1 0, 1; n n n t t t t            1 1 1 1 , . n n n n t t                 2 1 2 2 1 4 4 min cos , ( ) ( ) 1 ( ) T n n A A A A               . Звідси можна зробити висновки про вплив обумовленості та роз- поділу власних значень матриці TA A (матриці TAA ) на прискорення та сповільнення швидкості збіжності методу мінімальних похибок. Висновок. 5. Якщо існує кратне найменше значення  min TA A або група малих власних значень, то за умови погано обумовленої матриці A ітераційний процес в області min , що визначається умо- вою     2 2: min cos , cos ,n T Tw A A A A w w       , стає повільним. Ефективність будь-якого ітераційного методу повинна визначатися стратегією виходу з області min і наближенням до області max . Якщо матриця A погано обумовлена ( ) 1cond A A  , то в області min метод мінімальних похибок збігається повільно з кое- фіцієнтом:      2 22 2 21 1 1 1 min cos , 1 1 T A C A A A                 ,       max min T T A A A A A     . Висновок 6. Метод мінімальних похибок можна прискорити, об’єднавши алгоритм максимізації  2cos ,TA A r r   з процесом (4). Збіжність методу мінімальних нев’язок у випадку симетрич- ної додатно визначеної матриці. Поряд з ітераційним процесом (6)      1 1k k k ku u r      розглянемо процес для нев’язок      k k kTr A A    :      1 1k k kT kr r A r      (12) з матрицею k T kZ I A   . Виберемо початковий вектор  0 u u   . Позначимо через   i A множину власних значень матриці A , а Математичне та комп’ютерне моделювання 12 через  iw  — повну ортонормовану систему відповідних власних векторів матриці A , через   1 ( ) ,...,span mm i iH A w w   — підпростір, якому належить початковий вектор    0 0 u u      . Тоді аналогічно до дослідження методу мінімальних похибок одержимо результати. Лема 3. Для довільних значень параметрів k  вектори по- хибок  k  , 1, 2,...k  , методу мінімальних нев’язок для випадку 0TA A  належать підпростору  mH A , якому належить початко- вий вектор (0)  . Процес оптимізації в методі мінімальних нев’язок може бути за- вершений за m кроків, якщо параметри k вибирати з умови: 1 1 1 2 1 1 1 , ,..., ( ) ( ) ( ) m m m i i iA A A           . (13) Якщо розглянути стаціонарний ітераційний процес (12) з матри- цею TZ I A I A      , то оптимізація процесу збіжності буде забезпечуватися параметром  * 2 m M   , де  0 min i i m A  ,  max i i M A . Взагалі, межі m і M будуть за- лежати від вибору початкового вектора     1 0 : im A   ,   mi M A . Щоб дослідити швидкість збіжності методу мінімальних нев’язок, необхідно дослідити евклідову норму похибки. Лема 4. Для симетричної додатно визначеної матриці TA B B швидкість збіжності методу мінімальних нев’язок у довільній точці  k nx  є лінійною в евклідовій метриці і визначається коефіцієнтом           1 1 1 12 2 2, , 1 cos ,k k k kTK A K B B AA A                       1 1 1 12 2cos , cos ,k k k kBA B A                       1 1 1 12 22 cos , cos ,k k k kAA A BA B                   2 2 1 1 2 2 2 ,k k kK A       . (14) Доведення леми 4. На основі формули (6) маємо Серія: Фізико-математичні науки. Випуск 8 13              1 1 1 1* * 2 1 2 ,k k k k k k Ar r x x x x r Ar                                     1 1 1 1 2 2 1 2 22 2 1 1 2 2 , , 1 k k k k k k k k A r r r A r                                          2 11 1 2 2 1 11 2 , 2 , kk k k kk rA r r rA r                        . Використавши симетрію матриці TA A , виконаємо перетворення            2 1 1 1 1 1 2 , ,k k k k kT Tr B B B B BA B                      1 1 1 1, ,k k k kT T TAr r B BB B B B                2 1 1 1 2 ,k k kT TBB B BB B BA         ,             2 1 1 1 1 1 2 , ,k k k k kTr B B B             , (15) Підставимо (15) у   1 2 , kK A   , дістанемо формулу (14). Доведення леми 4 завершене. Висновок 7. Оптимальна швидкість збіжності (збіжність за один крок) методу мінімальних нев’язок досягається на власних прямих  :i iS x x x t      , t , T i i iB B     , оскільки кожна власна пара матриці TA B B визначає власну пару матриць 2A , BA . Якщо не оптимізувати процес збіжності методу мінімальних нев’язок, то він може збігатись повільніше від методу мінімальних похибок, оскільки коефіцієнт збіжності 2K може бути значно біль- шим 1K : 1 20 1K K   . Метод найшвидшого зменшення нев’язки. Якщо параметри k визначити за формулою (5)       2 2 1 1 1 2 2 1 ,k k kT T T T k A r AA r A A A r        , Математичне та комп’ютерне моделювання 14 то процедура мінімізації норми нев’язок ітераційного процесу  ku      1 1k kT ku A r     збігається для довільних невироджених матриць A . Результати досліджень швидкості збіжності методу (5) сформу- люємо як висновки леми. Лема 5. Для довільної невиродженої матриці ( )nA M  швид- кість збіжності методу найшвидшого зменшення нев’язок у довільній точці ( )k nx  є лінійною в евклідовій метриці і визначається коефі- цієнтом        1 1 12 3 , 1 cos ,k k kTK A AA A A                    1 1 1 12 2cos , 2 cos ,k k k kT TA A AA A A                   2 2 1 3 2 2 ,k k kK A       . (16) Доведення проводиться на основі дослідження квадрату евклі- дової норми вектора похибок. Метод найшвидшого спуску (SDM). Дослідимо швидкість збіж- ності методу (7) для симетричної додатно визначеної матриці TA B B :              2 1 1 12 1 1, k k k k k k r r A r r                . Лема 6. Для симетричної додатно визначеної матриці TA B B , швидкість збіжності методу найшвидшого спуску у довільній точці ( )k nx  є лінійною в евклідовій метриці і визначається коефіцієнтом           1 1 1 12 4 4, , 1 cos ,k k k kTK A K B B BA B                        1 1 1 12 2cos , 2 cos ,k k k kA BA B             ,       2 2 1 1 4 2 2 ,k k kK A       . (17) Доведення леми ґрунтується на співвідношеннях (15). Висновок 8. Методи мінімальних похибок (4), найшвидшого спуску (7), мінімальних нев’язок (6), найшвидшого зменшення нев’язок (5), мають лінійну швидкість збіжності. Для погано обумов- лених матриць, існують області повільної швидкості збіжності min , які визначаються умовами  2 1 min cos ,BA B        ,  2 1 min cos ,TA A        . Серія: Фізико-математичні науки. Випуск 8 15 Управління швидкістю збіжності методів (4)—(7) на основі мак- симізації функціоналу  2cos ,TA A r r   дозволяє прискорити їх швид- кість збіжності. Покажемо, що коефіцієнти збіжності методів (4)—(7) є деякими многочленними виразами. Нехай A — симетрична додатно визначе- на матриця, TA B B (або TBB ). Доведемо, що     2 2 2 2 1 1 min cos , min cos ,T TB B BB B B               (ана- логічно     2 2 2 2 1 1 min cos , min cos ,T T T TBB B BB B               ). Розкладемо вектор   по системі власних векторів матриці TB B , 1 n i i i c      , T i i iB B     (власні значення ( )T i B B взяті з їх кратностями): 1 n T i i i i B B c       . Вираз  2cos ,TBB B B    перетворимо так:     2 2 22 12 2 2 2 2 3 22 1 1 , cos , n T i i iT n nT i i i i i i c BB B B BB B B BB B B c c                              . Позначимо 2 0i i it c   , [1: ]i n , тоді   2 12 1 1 2 1 min cos , min n i i iT nt i i i t BB B B t                      , 1[ ,..., ]Tnt t t  . Заміною змінних вираз  2cos ,TBB B B    приведений до екві- валентного виразу для  2cos ,TBB     , що означає рівність їх екстре- мальних значень. Таким чином, коефіцієнти збіжності методів (4)— (7) в області min можна подати як многочленні вирази:                 2 1 3 2 2 2 2 2 3 2 2 4 min , 1 , min cos , ; min , 1 (2 ), min cos , ; min , 1 (2 ), min cos , ; min , 1 (2 ), min cos , , T T T T T T T T K A A A A K BB BB K A A A A K BB BB                                                   (18) Математичне та комп’ютерне моделювання 16 де TB B A . З формули (18) випливає теоретичне обґрунтування практичних вис- новків, які отримані на основі тестових досліджень в роботах [6; 10]: сповільнення швидкості збіжності ітераційних методів розв’язання сис- теми рівнянь A x b  залежить, як від обумовленості матриці A , так і від групування власних значень. Якщо наближатись до області max , де  2max cos , 1C      , то швидкість збіжності методів (4)—(7) буде прискорюватись, оскільки коефіцієнти збіжності 0iK  , 1,2,3, 4i  . Одержані результати дають змогу побудувати алгоритм мінімаль- них похибок (аналогічно мінімальних нев’язок, найшвидшого зменшен- ня нев’язки, найшвидшого спуску) з керуванням процесу збіжності. Алгоритм. 1. Вибрати довільний вектор  0x  і виконати декіль- ка ітерацій [4] для наближення до області max в кулі  0 * 2 2 x x x x       . Знайдений вектор позначити через  0u  . 2. Для 1,2,...k  виконати (алгоритм мінімальних похибок (1), (4))          2 2 1 1 1 1 2 2 ,k k k k kT T k ku u A r r A r            з аналізом значення функціоналу       2cos ,k k kTAA r r c   . Якщо   0 kc  ( 0.5)  то, поклавши    0 1kx u    , перейти на п.1. У протилежному випадку. 3. Виконати один із тестів на збіжність [4; 15] і перейти на п.2. Аналогічно записується алгоритм для методу мінімальних нев’я- зок, найшвидшого зменшення нев’язки, найшвидшого спуску. Умови прискорення швидкості збіжності ітераційного мето- ду Гауса-Зейделя. Ітераційний процес Гауса-Зейделя наближеного розв’язування системи Ax b  ,  nA M  ,  intb A  , rank A n , з використанням базису   1 n i i E e    одиничних векторів, має за мету обнуління компонент вектора нев’язки. Нехай вектор  0 x x   — довільний вектор простору n . Вибе- ремо таку пару одиничних векторів  0 ie  ,  0 je  , щоб проекція вектора  0x  на гіперплощину   0 , 0T jA e    , у напрямку вектора  0 ie  міні- Серія: Фізико-математичні науки. Випуск 8 17 мізувала норму вектора похибки x x      . Якщо цей процес повто- рити для всіх 0,1,...k  , то дістанемо алгоритм Гауса-Зейделя                1 , , kk i kk k ik kT j i r e x x e A e e           (19) і послідовність норм векторів похибок:      2 2 1 2 2 k k kK     ,     ( ) cos , kkk i it e   (20) ( ) ( ) ( ) ( ) 2 , ,1 2 ( )k k k k i j i i jK t    ,           ( ) , cos , cos , kk T i k i j k kT j i A e A e e        , де    ,k k i je e   — одиничні вектори, що обираються на  1k  -му кроці,     k kx x      ,  kK — коефіцієнт збіжності. Дослідимо на мінімум коефіцієнт збіжності   ( ) 21 2k k iK t    по параметру   , матимемо ( ) 2 min0 min 1 1kK     за умови   min k it  ; ( )0 1kK  за умови ( )0 2 k it  або ( )2 0k it   . (21) Нерівності (21) визначають, як умови збіжності методу Гауса- Зейделя на k -му кроці, так і умови прискорення збіжності. Умови збіжності (21) практично складно використовувати, оскі- льки вектор похибки  k  невідомий, тому проаналізуємо норму век- тора нев’язки:    2 2 1 ( ) 2 2 k kkr C r    ,                          2 ( ) 2 cos , cos , 1 2 cos , cos , cos , k kk k i ikkk T ik k k k j i j i r e r e C r A e e Ae e Ae              , (22)     ( ) cos ,k kk T i iq r A e   ,          ( ) , cos , cos ,k k k kk i j i i jp r e e Ae     . Умова прискорення збіжності послідовності норм нев’язок, сформова- них методом Гауса-Зейделя на k -му кроці, визначається нерівністю ( ) ( ) ,0 2k k i j ip q  . (23) Математичне та комп’ютерне моделювання 18 Метод мінімізації нев’язок і похибок у просторах AE і TA E . Процес Гауса-Зейделя, з однієї сторони, має просту реалізацію, оскі- льки використовує базис E одиничних векторів, з другої сторони, слабко збігається (або взагалі розбігається) для систем з довільними матрицями і, по-третє, умови вибору оптимальної пари векторів    ,k k i je e   вимагають додаткових обчислень. Розкладемо вектор похибки  0 x x x         по базису E :       0 0 0* * 1 1 1 n n n i i i i i i i i i x x e A x x A e r Ae                      , (24) дістанемо розклад вектора нев’зки. Якщо у розкладі (24) залишити окремі компоненти, то дістанемо сукупність векторів нев’язок  0 i i ir r Ae     . Виберемо параметри i з умови найшвидшого змен- шення норми вектора нев’язки, що еквівалентно розв’язуванню міні- максної задачі: [1: ],i n      22 20 0 2 2 22 min max min 2 , 1: i i i i ir r r Ae Ae i ni i                      (25) Алгоритм методу мінімальних нев’язок у просторі AE . До по- чатку ітераційного процесу обчислити норми вектор-стовпців матриці A :  2 2 1 \|\| \|\| n i i Ae   . Вибрати довільний вектор  0x  . Для всіх 0,1,...k   обчислити нев’язку    k kr A x b    та  kTA r  ;  знайти індекс;      2 2 0 0 0 2 2[1: ] [1: ] 2 2 , , : max max \|\| \|\| \|\| \|\| T i i Ti n i n i i r A e A r e i i A e A e           ;  сформувати вектор       0 0 0 1 2 2 ,k ik k i i r A e x x e Ae          . (26) Продовжити процес до виконання умови   0 2 kr   . Лема 7. Послідовність норм нев’язок   2 kr  для k  строго монотонно збігається до нуля для довільної матриці  nA M  , rank A n , і для довільного вектора  0x  . Серія: Фізико-математичні науки. Випуск 8 19 Доведення. Для всіх 1, 2,3,...k  з формули (26) випливає, що якщо існують індекси    0 1:ki n , для яких   0 , 0k ir Ae    , то послі- довність   2 kr  монотонно спадає. Якщо     1: , 0k ii n r Ae     , то   0kr   , оскільки система векторів   1 n i i Ae   лінійно незалежна. Доведення леми 7 завершене. Якщо у розкладі (24) залишити p компонент  1,..., p pi i I ,   , 0kT iA r e    , pi I , то дістанемо задачу:        22 2 2 minmax minmax 2 , , p p p p p k k p i i i j i j i I i I i I i I j I r r r Ae Ae Ae                             . Для фіксованої множини індексів pI задача зведеться до розв’язан- ня системи рівнянь відносно вектора   1 ,..., p T i i    з симетричною до- датно визначеною матрицею B і вектором правих частин f  : B f   ,   , , p i j i j I B Ae Ae        ,   , p T k i i I f r Ae          . (27) Знову розкладемо вектор похибки    0 0 x x      , але по базису   1 nT i i A e   , матимемо    0 0 1 n T i i i x x A e          . (28) Якщо у розкладі (28) залишити окремі доданки, то дістанемо век- тори похибок  0 T i i iA e       . Знайдемо параметри i з умови найшвидшого зменшення норми вектора похибки:         2 22 0 0 2 2 21: 1: 2 min max min max 2 , i i T i i i i i i n i n r e A e                      . (29) Алгоритм методу мінімальних похибок у просторі TA E . До початку ітераційного процесу обчислити 2 2 1 n T i i A e         . Вибрати дові- льний вектор  0x  . Для всіх 0,1,...k  Математичне та комп’ютерне моделювання 20  обчислити нев’язку    k kr A x b    ;  знайти індекс     2 2 0 21: : max ,k T i i i n i i r e A e            ;  сформувати вектор       0 0 0 1 2 2 ,k ik k T i T i r e x x A e A e          . (30) Продовжити процес до виконання умови   0 2 kr   . Лема 8. Послідовність норм похибок   2 k  для k  строго монотонно збігається до нуля для довільної матриці  nA M R , rank A n , і для довільного вектора  0x  . Доведення леми 8 проводиться аналогічно доведенню леми 7. Якщо у розкладі (28) залишити p компонент  1,..., p pi i J , для яких   , 0k ir e    , pi J , то, аналогічно (27), задача зведеться до зна- ходження вектора   1 , ..., p T i i    , шляхом розв’язання системи рівнянь C d   ,   , , p T T i j i j J C A e A e        ,   , p T k i i J d r e          , (31) з симетричною додатно визначеною матрицею C . Якщо для систем індексів pi I , або pi J відповідно вектори  i i I p Ae   або  T i i J p A e   взаємно ортогональні, то матриці B або C стануть діагональними. Якщо, крім того, матриця A симетрична, то B C , але f d   . Теорема. Послідовність норм векторів нев’язок, обчислених ме- тодом мінімальних нев’язок (26) у просторі AE збігається швидше, ніж послідовність норм векторів нев’язок, обчислених методом Гау- са-Зейделя (22) у просторі E . Якщо на k -му кроці існує одиничний вектор  k ie  такий, що          cos , cos ,k k k kT i i ie e e A e     , [1: ]j n  , то доцільно для міні- Серія: Фізико-математичні науки. Випуск 8 21 мізації норми вектора похибок використовувати метод Гаусса- Зейделя (20), у протилежному випадку, – метод мінімальних похибок (30). Такий процес прискорить швидкість збіжності методу Гаусса- Зейделя для розв’язання системи A x b  з довільними невиродже- ними матрицями ( )nA M R , rank A n . Доведення теореми засновано на дослідженні коефіцієнта збіжності. Результати 1. Досліджено умови, що прискорюють швидкість збіжності методів мінімальних похибок, мінімальних нев’язок, найшвидшого змен- шення нев’язки, найшвидшого спуску Гауса-Зейделя. 2. Досліджено, як впливає розподіл власних значень та обумовле- ність матриці переходу на швидкість збіжності ітераційних мето- дів. Описані області min max,  . 3. Запропонована модифікація алгоритму мінімальних похибок (мі- німальних нев’язок) з керуванням швидкістю процесу збіжності. 4. Показана залежність процесу збіжності ітераційних методів від вибору вектора початкового наближення. 5. Для сіткових рівнянь запропоновані методи мінімальних похибок та нев’язок у просторах TA E , AE , які прискорюють швидкість збіжності ітерацій Гауса-Зейделя. Список використаних джерел: 1. Абрамчук В. С. О перспективности методов направленного поиска реше- ния систем Ax = f с плохо обусловленными матрицами / В. С. Абрамчук // Доп. НАН Украины. Сер. Б. — 1995. — № 2. — С. 5–7. 2. Абрамчук В. С. Ефективні ітераційні методи розв’язування систем ліній- них рівнянь / В. С. Абрамчук, І. В. Абрамчук, А. Вешемірський // Вісник Львівського університету. Сер. Прикладна математика та інформатика. — 2007. — Вип. 12. — С. 5–12. 3. Абрамчук В. С. Обоснование эффективности методов направленного поиска / В. С. Абрамчук // Доп. НАН України. — 1997. — № 11. — С. 7–12. 4. Абрамчук В. С. Ітераційні методи розв’язування систем лінійних рівнянь з довільними невиродженими матрицями / В. С. Абрамчук, І. В. Абрам- чук // Математичне та комп'ютерне моделювання. Серія: Фізико- математичні науки: зб. наук. праць. — Кам’янець-Подільський : Кам’я- нець-Подільський національний університет імені Івана Огієнка, 2012. — Вип. 6. — С. 3–16. 5. Воеводин В. В. Матрицы и вычисления / В. В. Воеводин, Ю. А Кузне- цов. — М. : Наука, 1984. — 320 с. 6. Деммель Дж. Вычислительная линейная алгебра / Дж. Деммель. — М. : Мир, 2001. — 429 с. 7. Зверев В. Г. Модифицированный полилинейный метод решения разност- ных эллиптических уравнений / В. Г. Зверев // ЖВМ и МФ. — 1998. — Т. 38. — № 9. — С. 1553–1562. Математичне та комп’ютерне моделювання 22 8. Ильин В. П. Методы бисопряженных направлений в подпространствах Крылова / B. П. Ильин // Сибирский журнал индустриальной математи- ки. — 2008. — Т. ХІ. — № 4 (36). — C. 47–60. 9. Ланкастер К. Математическая экономика. / К. Ланкастер ; под ред. Д. Б. Юдина. — М. : Советское радио, 1972. — 464 с. 10. Ортега Дж. Введение в параллельные и векторные методы решения ли- нейных систем / Дж. Ортега. — М. : Мир, 1991. — 364 с. 11. Тыртышников Е. Е. Методы численного анализа: Курс лекций / Е. Е. Тыр- тышников. — М. : ИВМ РАН, 2006. — 291 с. 12. Тыртышников Е. Е. Матричный анализ и линейная алгебра / Е.Е. Тырты- шников. — М. : Физматлит, 2007. — 480 с. 13. Фомин А. А. Сравнение эффективности высокоскоростных методов ре- шения разностных эллиптических СЛАУ / А. А. Фомин, Л. Н. Фомина // Вестник Томского университета. Сер. Математика и механика. — 2009. — № 2. — C. 71–77. 14. Хейгеман Л. Прикладные итерационные методы / Л. Хейгеман, Д. Янг ; пер. с англ. — М. : Мир, 1986. — 448 с. 15. Хорн Р. Матричный анализ / Р. Хорн, Ч. Джонсон. — М. : Мир, 1989. — 655 с. 16. Yousef Saad. Iterative Methods for Sparse Linear Systems / Saad Yousef. — N.Y. : PWS Publ., 1996. — 460 p. Both the conditions account for the slowing of convergence rate of iterative methods of Ax b  systems solving and the conditions allowing accelerate the convergence of iteration process are investigated. Key words: minimal error method, Minimal Residual method— MinRES, Residual norm Steepest Descent — RnSD, Steepest Descent Me- thod — SDM, Gauss-Seidel method. Отримано: 25.02.2013 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /All /Binding /Left /CalGrayProfile (Gray Gamma 2.2) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (Coated FOGRA27 \050ISO 12647-2:2004\051) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Warning /CompatibilityLevel 1.3 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.1000 /ColorConversionStrategy /sRGB /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo false /PreserveFlatness false /PreserveHalftoneInfo false /PreserveOPIComments false /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Remove /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true /Arial-Black /Arial-BlackItalic /Arial-BoldItalicMT /Arial-BoldMT /Arial-ItalicMT /ArialMT /ArialNarrow /ArialNarrow-Bold /ArialNarrow-BoldItalic /ArialNarrow-Italic /ArialUnicodeMS /CenturyGothic /CenturyGothic-Bold /CenturyGothic-BoldItalic /CenturyGothic-Italic /CourierNewPS-BoldItalicMT /CourierNewPS-BoldMT /CourierNewPS-ItalicMT /CourierNewPSMT /Georgia /Georgia-Bold /Georgia-BoldItalic /Georgia-Italic /Impact /LucidaConsole /Tahoma /Tahoma-Bold /TimesNewRomanMT-ExtraBold /TimesNewRomanPS-BoldItalicMT /TimesNewRomanPS-BoldMT /TimesNewRomanPS-ItalicMT /TimesNewRomanPSMT /Trebuchet-BoldItalic /TrebuchetMS /TrebuchetMS-Bold /TrebuchetMS-Italic /Verdana /Verdana-Bold /Verdana-BoldItalic /Verdana-Italic ] /AntiAliasColorImages false /CropColorImages false /ColorImageMinResolution 150 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 150 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >> /ColorImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /AntiAliasGrayImages false /CropGrayImages false /GrayImageMinResolution 150 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 150 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >> /GrayImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /AntiAliasMonoImages false /CropMonoImages false /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects true /CheckCompliance [ /PDFX1a:2001 ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (None) /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064506390020064506420627064A064A0633002006390631063600200648063706280627063906290020062706440648062B0627062606420020062706440645062A062F062706480644062900200641064A00200645062C062706440627062A002006270644062306390645062706440020062706440645062E062A064406410629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043f043e04340445043e0434044f044904380020043704300020043d043004340435043604340435043d0020043f044004350433043b04350434002004380020043f04350447043004420020043d04300020043104380437043d0435044100200434043e043a0443043c0435043d04420438002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e55464e1a65876863768467e5770b548c62535370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc666e901a554652d965874ef6768467e5770b548c52175370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002000760068006f0064006e00fd00630068002000700072006f002000730070006f006c00650068006c0069007600e90020007a006f006200720061007a006f007600e1006e00ed002000610020007400690073006b0020006f006200630068006f0064006e00ed0063006800200064006f006b0075006d0065006e0074016f002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000650067006e006500720020007300690067002000740069006c00200064006500740061006c006a006500720065007400200073006b00e60072006d007600690073006e0069006e00670020006f00670020007500640073006b007200690076006e0069006e006700200061006600200066006f0072007200650074006e0069006e006700730064006f006b0075006d0065006e007400650072002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200075006d002000650069006e00650020007a0075007600650072006c00e40073007300690067006500200041006e007a006500690067006500200075006e00640020004100750073006700610062006500200076006f006e00200047006500730063006800e40066007400730064006f006b0075006d0065006e00740065006e0020007a0075002000650072007a00690065006c0065006e002e00200044006900650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000520065006100640065007200200035002e003000200075006e00640020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ENU (Use these settings to create Adobe PDF documents suitable for reliable viewing and printing of business documents. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000640065002000410064006f00620065002000500044004600200061006400650063007500610064006f007300200070006100720061002000760069007300750061006c0069007a00610063006900f3006e0020006500200069006d0070007200650073006900f3006e00200064006500200063006f006e006600690061006e007a006100200064006500200064006f00630075006d0065006e0074006f007300200063006f006d00650072006300690061006c00650073002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e400740074006500690064002000e4007200690064006f006b0075006d0065006e00740069006400650020007500730061006c006400750073007600e400e4007200730065006b0073002000760061006100740061006d006900730065006b00730020006a00610020007000720069006e00740069006d006900730065006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f006200650020005000440046002000700072006f00660065007300730069006f006e006e0065006c007300200066006900610062006c0065007300200070006f007500720020006c0061002000760069007300750061006c00690073006100740069006f006e0020006500740020006c00270069006d007000720065007300730069006f006e002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003b103be03b903cc03c003b903c303c403b7002003c003c103bf03b203bf03bb03ae002003ba03b103b9002003b503ba03c403cd03c003c903c303b7002003b503c003b903c703b503b903c103b703bc03b103c403b903ba03ce03bd002003b503b303b303c103ac03c603c903bd002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05d405e905ea05de05e905d5002005d105d405d205d305e805d505ea002005d005dc05d4002005db05d305d9002005dc05d905e605d505e8002005de05e105de05db05d9002000410064006f006200650020005000440046002005e205d105d505e8002005d405e605d205d4002005d505d405d305e405e105d4002005d005de05d905e005d4002005e905dc002005de05e105de05db05d905dd002005e205e105e705d905d905dd002e002005de05e105de05db05d90020005000440046002005e905e005d505e605e805d5002005e005d905ea05e005d905dd002005dc05e405ea05d905d705d4002005d105d005de05e605e205d505ea0020004100630072006f006200610074002005d5002d00410064006f00620065002000520065006100640065007200200035002e0030002005d505d205e805e105d005d505ea002005de05ea05e705d305de05d505ea002005d905d505ea05e8002e> /HRV (Za stvaranje Adobe PDF dokumenata pogodnih za pouzdani prikaz i ispis poslovnih dokumenata koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF00410020006800690076006100740061006c006f007300200064006f006b0075006d0065006e00740075006d006f006b0020006d00650067006200ed007a00680061007400f30020006d0065006700740065006b0069006e007400e9007300e900720065002000e900730020006e0079006f006d00740061007400e1007300e10072006100200073007a00e1006e0074002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c00200068006f007a006800610074006a00610020006c00e9007400720065002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA (Utilizzare queste impostazioni per creare documenti Adobe PDF adatti per visualizzare e stampare documenti aziendali in modo affidabile. I documenti PDF creati possono essere aperti con Acrobat e Adobe Reader 5.0 e versioni successive.) /JPN <FEFF30d330b830cd30b9658766f8306e8868793a304a3088307353705237306b90693057305f002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a3067306f30d530a930f330c8306e57cb30818fbc307f3092884c3044307e30593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020be44c988b2c8c2a40020bb38c11cb97c0020c548c815c801c73cb85c0020bcf4ace00020c778c1c4d558b2940020b3700020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b0075007200690065002000740069006e006b006100200070006100740069006b0069006d006100690020007000650072017e0069016b007201170074006900200069007200200073007000610075007300640069006e0074006900200076006500720073006c006f00200064006f006b0075006d0065006e007400750073002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020007000690065006d01130072006f00740069002000640072006f016100610069002000620069007a006e00650073006100200064006f006b0075006d0065006e007400750020006100700073006b006100740065006900200075006e0020006400720075006b010101610061006e00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken waarmee zakelijke documenten betrouwbaar kunnen worden weergegeven en afgedrukt. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d002000650072002000650067006e0065007400200066006f00720020007000e5006c006900740065006c006900670020007600690073006e0069006e00670020006f00670020007500740073006b007200690066007400200061007600200066006f0072007200650074006e0069006e006700730064006f006b0075006d0065006e007400650072002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f0020006e00690065007a00610077006f0064006e00650067006f002000770079015b0077006900650074006c0061006e00690061002000690020006400720075006b006f00770061006e0069006100200064006f006b0075006d0065006e007400f300770020006600690072006d006f0077007900630068002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f00620065002000500044004600200061006400650071007500610064006f00730020007000610072006100200061002000760069007300750061006c0069007a006100e700e3006f002000650020006100200069006d0070007200650073007300e3006f00200063006f006e0066006900e1007600650069007300200064006500200064006f00630075006d0065006e0074006f007300200063006f006d0065007200630069006100690073002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e007400720075002000760069007a00750061006c0069007a00610072006500610020015f006900200074006900700103007200690072006500610020006c0061002000630061006c006900740061007400650020007300750070006500720069006f0061007201030020006100200064006f00630075006d0065006e00740065006c006f007200200064006500200061006600610063006500720069002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002000760068006f0064006e00fd006300680020006e0061002000730070006f013e00610068006c0069007600e90020007a006f006200720061007a006f00760061006e006900650020006100200074006c0061010d0020006f006200630068006f0064006e00fd0063006800200064006f006b0075006d0065006e0074006f0076002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020007000720069006d00650072006e006900680020007a00610020007a0061006e00650073006c006a00690076006f0020006f0067006c00650064006f00760061006e006a006500200069006e0020007400690073006b0061006e006a006500200070006f0073006c006f0076006e0069006800200064006f006b0075006d0065006e0074006f0076002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f0074002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002c0020006a006f0074006b006100200073006f0070006900760061007400200079007200690074007900730061007300690061006b00690072006a006f006a0065006e0020006c0075006f00740065007400740061007600610061006e0020006e00e400790074007400e4006d0069007300650065006e0020006a0061002000740075006c006f007300740061006d0069007300650065006e002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d00200070006100730073006100720020006600f60072002000740069006c006c006600f60072006c00690074006c006900670020007600690073006e0069006e00670020006f006300680020007500740073006b007200690066007400650072002000610076002000610066006600e4007200730064006f006b0075006d0065006e0074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005400690063006100720069002000620065006c00670065006c006500720069006e0020006700fc00760065006e0069006c0069007200200062006900720020015f0065006b0069006c006400650020006700f6007200fc006e007400fc006c0065006e006d006500730069002000760065002000790061007a0064013100720131006c006d006100730131006e006100200075007900670075006e002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043d0430043404560439043d043e0433043e0020043f0435044004350433043b044f043404430020044204300020043404400443043a0443002004340456043b043e04320438044500200434043e043a0443043c0435043d044204560432002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043f043e04340445043e0434044f04490438044500200434043b044f0020043d0430043404350436043d043e0433043e0020043f0440043e0441043c043e044204400430002004380020043f04350447043004420438002004340435043b043e0432044b044500200434043e043a0443043c0435043d0442043e0432002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AllowImageBreaks true /AllowTableBreaks true /ExpandPage false /HonorBaseURL true /HonorRolloverEffect false /IgnoreHTMLPageBreaks false /IncludeHeaderFooter false /MarginOffset [ 0 0 0 0 ] /MetadataAuthor () /MetadataKeywords () /MetadataSubject () /MetadataTitle () /MetricPageSize [ 0 0 ] /MetricUnit /inch /MobileCompatible 0 /Namespace [ (Adobe) (GoLive) (8.0) ] /OpenZoomToHTMLFontSize false /PageOrientation /Portrait /RemoveBackground false /ShrinkContent true /TreatColorsAs /MainMonitorColors /UseEmbeddedProfiles false /UseHTMLTitleAsMetadata true >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /BleedOffset [ 0 0 0 0 ] /ConvertColors /ConvertToRGB /DestinationProfileName (sRGB IEC61966-2.1) /DestinationProfileSelector /UseName /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements true /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles true /MarksOffset 6 /MarksWeight 0.250000 /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PageMarksFile /RomanDefault /PreserveEditing true /UntaggedCMYKHandling /UseDocumentProfile /UntaggedRGBHandling /LeaveUntagged /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [600 600] /PageSize [419.528 595.276] >> setpagedevice

Дослідження швидкості збіжності класичних ітераційних методів розв’язування систем Ax = b великих порядків

Репозитарії

Схожі ресурси