Анализ ошибок округления решения трехдиагональных систем линейных алгебраических уравнений тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

АКАДЕМИЯ НАУК СССР ОРДЕНА ЛЕНИНА СИБИРСКОЕ ОТДЕЛЕНИЕ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

ПИНКИНА НАТАЛЬЯ АНАТОЛЬЕВНА

УДК 519.612.2

АНАЛИЗ ОШИБОК ОКРУГЛЕНИЯ РЕШЕНИЯ ГРВДИАГОНАЛБНЫХ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЯ

Специальность 01.01.07 - вычислительная математика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск 1991

Работа выполнена в Вычислительном центре СО АН СССР.

Научный руководитель: доктор физико-математических наук, профессор В.П.Ильин.

Официальные оппоненты: доктор физико-математических наук, профессор А.Ф.Воеводин, кандидат физико-математических наук, доцент В.И.Костин.

Ведущая организация: Красноярский Вычислительный центр СО АН СССР.

Защита состоится 1991 г. в миг.

на заседании специализированного совета К 002.10.01 по . присуждению ученой степени кандидата наук в Вычислительном центре СО АН СССР по адресу:

630090, НовосиОирск-ЭО, пр. ак. Лаврентьева, Б.

С диссертацией можно ознакомиться в читальном зале отделения ГОНГЕ (Новоси0нрск-90, пр. ак. Лаврентьева, 6).

Автореферат разослан ¿З^^&^^тээ! г.

Ученый секретарь специализированного совета кандвдат физико-математических наук / Ю.И.Кузнецов

I. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность тема. Исследование численных методов решения систем линейных алгебраических уравнений (СЛАУ) является одной из ванне йшх задач в численном анализе. Частным случаем СЛАУ являются системы с трехдиагональными матрицами, возникающие, например, при разностной аппроксимации основных уравнений математической физики. Кроме того, решение таких систем входит как составная часть во многие другие задачи.

Хотя теория решения СЛАУ достаточно проста, практическая реализация численных методов, из-за их чувствительности к влиянию ошибок округления, вызывает немало трудностей. Возросшая сложность задач приводит к необходимости проведения трудоемких расчетов. Большие задачи, чаде всего обладающие свойством накапливать ошибки округления, требуют их тщательного анализа, поэтому изучение численной устойчивости методов является весьма вакной и актуальной задачей.

Целью диссертационной работа является:

- построение априорных и реализуема на ЗВМ апостериорных оценок точности решения трехдиагональннх СЛАУ;

- сравнительный анализ численной устойчивости прямых методов решения трехдиагональннх СЛАУ;

- матричная интерпретация прямых методов линейной алгебры.

Методика исследования. Априорные и апостериорные оценки точности решения построены на основе прямого анализа ошибок округления, первые - аналитическим преобразованием формул вычисления погрешностей, вторые - частично-пооперационным функциональным методом.

Научная новизна изложенных в работе результатов заключается в следующем:

- построены априорные и апостериорные оценки точности решения на ЭВМ методов: прогонки и его модификаций, ортогональной прогонки, циклической редукции, двух способов "распараллеливания" прогонки;

- предложены матричные- интерпретации: общей схемы редукции, методов А.Ф.Воеводина и Д.Ивенса решения систем с постоянными коэффициентами, алгоритма "распараллеливания" прогонки с использованием техники сопровождающих функций;

- осуществлен сравнительный анализ численной устойчивости прямых методов решения трехдиагональных СЛАУ, выработаны рекомендации по

организации вычислений для повышения численной устойчивости.

Достоверность содержащихся в диссертации результатов подтверждена теоретическим обоснованием выводимых в работе оценок, тестовыми расчетами, сравнением с точным решением, сопоставлением с результатами других направлений исследования ошибок округления.

Научная и практическая ценность. Рассмотренные в диссертации метода и полученные оценки ошибок округления реализованы в виде комплекса программ, с помощью которого помимо решения задачи одним из предложенных методов можно найти и оценку точности вычисленного решения. Комплекс программ сдан в ГосФАП (Алгоритмы и программы. Информационный бюллетень. -М.: ВИНИТИ, 1990. -JH2. -С.5. Инв. JÉ60900000903).

Априорные оценки зависят от а) точности выполнения арифметических операций на конкретной ЭВМ, б) соотношений между коэффициентами системы, в) порядка системы (иногда зависимость от порядка отсутствует); при их вычислении не требуется знания числа обусловленности.

Предлагаемый в диссертации аппарат построения апостериорных оценок точности решения позволяет находить погрешность решения без чрезмерных временных затрат и дополнительного расхода оперативной памяти.

Апробация работы. Основные результаты работы докладывались

- на конференциях: Всесоюзная конференция по однородным средам и систолическим структурам (г.Львов, 1988г., 1990г.), 5-я Сибирская школа по вычислительной математике (г.Новосибирск, 1988г.),Всесоюзная конференция "Новые подходы к решению дифференциальных уравнений" (г.Дрогобыч, 1989г.), XXI региональная школа-конференция (г.Свердловск, 1990г.);

- на семинарах: "Метода вычислительной и прикладной математики" ВЦ СО АН СССР (г.Новосибирск), "Численное решение дифференциальных уравнений" ИГШЫ (г.Львов),се?яшары Крас.ВЦ СО АН СССР (г.Красноярск), кафедры вычислительной математики Краен.ГУ (г.Красноярск), ИГ СО АН ССОР (г.Новосибирск).

Публикации. Основные результаты диссертации опубликованы в работах [ I-II].

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, трех приложений и списка цитируемой литературы. Объем содержательной части диссертации - 138 страниц, прило-

жений - 56 страниц, списка литературы - 28 страниц. Работа включает 17 таблиц и 10 рисунков, список литературы из 283 наименований.

И. СОДЕРЖШЕ РАБОТЫ

Во введении приводится обзор основных отечественных и зарубежных работ по исследуемой теме, обсуждается понятие численной устойчивости в определениях, сформулированных С.К.Годуновым, В.С.Рябеньким, Р.Бауэром, В.Н.Фаддеевой, Д.Ивенсом, Дж.Уилкинсояом и др. Рассматривается краткая характеристика основных направлений в изучении ошибок округления - интервального, прямого, обратного анализов, теории графов, статистического и асимптотического подходов. Здесь же дается постановка задачи - построение априорных и апостериорных оценок точности решения трехдаагональных СЛАУ вида

-а.х .rt.t-o.s =1, i=1,...,п, а =о =0. (I)

X t-1 1. V 1. 1 ' " * Г>

Главным образом изучается численная устойчивость систем (I), удовлетворяющих условию строгого

|Ъ. |=|а 1+Ю. |+ес, t=1....... б. » а > О (2)

или нестрогого

IbJ^laJ + lo.l, (V)

tal loj

-+ - = а'°' £ aá 1 (2")

Ib.l |b.|

(в (2') и (2") хотя бы для одного i неравенство строгое) диагонального преобладания. Иногда условие (2') заменяется на

Ib. | = |ас! + |о. I, i=2,...,n-1. Ib. OlaJ + lo.1, i=1 или(и) п. (2"')

Предполагается неразложимость матрицы системы а # о, Ф о,

1=2.....п—1, о^ о, an?í о, в противном случае система распадается

на независимо решаемые подсистемы.

Во введении также формулируются задачи исследования, кратко излагается структура диссертации и ее содержание.

Первые две главы посвященн изучению численной устойчивости

прямых методов решения трехдиагональных СЛАУ и построению априорных оценок точности вычисленного решения.

В первой главе проводится анализ накопления погрешностей алгоритмов, в основе которых лекит факторизация матрицы системы. В первом, втором, третьем параграфах рассмотрены соответственно: хи-раз-ложение, модификации ьи-разлокения и од-разлокение.

Первый параграф посвяцен анализу ошибок округления метода прогонки и его модификаций: изменение направления счета, два варианта встречной прогонки (и две разновидности этих вариантов), замена в прогонке, замена в прогонке с изменением направления счета, использование замены прогоночного коэффициента во встречных прогонках.

Исследования, проведенные в п.1.1, связаны с изучением численной устойчивости систеш (I) при условии нестрогого диагонального преобладания (21). В п.1.1.1 на примере анализа накопления ошибок округления прогоночных коэффициентов ^ в методе прогонни обсувда-ются узловые моменты рассматриваемой методики исследования. Основные ограничения:

- строятся абсолютные оценки накопления погрешностей округления;

- изучаются лишь ошибки округления, возникаодие при реализации алгоритма на ЭВМ, коэффициенты систеш и правые части заданы точно;

- ограничения на допустимый порядок систеш в зависимости от точности машинной арифметики е и свойства коэффициентов системы рассматриваются в форме, аналогичной определенной в

Получаемые в первом параграфе оценки ошибок различных модификаций метода прогонки отражают однотипные закономерности в накоплении ошибок. Однако, на их основе в каждом конкретном случае можно выбрать более устойчивую модификацию метода. Для примера приведем оценку погрешности решения систеш (I) методом встречных прогонок (алгоритм I), суть которого в следующем: если 1 - любая точка индексного отрезка (1,п), то I) находятся прогоночные коэффициенты р.,г., 1=1,...,1, р., I, 1=а,...д-и; 2) вычисляется 3) проводится обратный ход прогонки для 1=1,...,1 и 1=1+1,...,п. В диссертации получена следующая оценка погрешности

л (п-1+1)(п-1) 1(1+1) 16x^1 « е(КСае(тах{-^- ,-§—}+|х11тах{п-1,1}) П 1Р1НсИ-

П.Ильин, Ю.И.Кузнецов. Трехдиагональные матрицы и их приложения. -М., Наука. -1985.

+11)3X13^1 (Cae(2l-i-1 >1/2+0^6(311(1-1)+! (iJ-1 ) )+i).

Здесь ж = max {ae aL}, ae = max ae ,

i=i.....i '' •> i 1

j=n.----1

„ i ~ „ i '

Vbn >7kl. Tk= s--. * = П lTkl, 7k—-

k=2 к k=2 к

K,C,61 - константы, определенные в [II], ipki < 1, ipki 41.

В п.1.2 рассматривается устойчивость метода прогонки при условии строгого диагонального преобладания (2). Оценки накопления погрешностей округления имеют вид:

иГ* 1

|бх . I < 6А- , U = - < 1, d=max{ la I, |о I },

' 1-М 8 1

1 + -

d

At- константа, определенная в [4].

В этом не пункте отдельно исследуется накопление ошибок при решении на ЭВМ серии систем вида (I), правая часть каждой из последующих получается использованием решения предыдущей. Такие системы возникают, например, при неявных аппроксимациях параболических уравнений. Получена следующая оценка погрешности:

j 1 -м1" 1 -ае"*1

|8х .1 < £А--, 1=1,...,п, о'=1,...,т, (3)

1 1-м 1-х

х - параметр [4]. Соотношение (3) при х < 1 характеризует ограниченность ошибок округления при решении серии систем константой, не зависящей ни от числа уравнений п в каждой системе, ни от количества систем т.

Во втором параграфе изучаются модификации ш-разлокения. Первая из них связана с использованием произвола в выборе диагональных элементов одной из матриц ь или о - рассматривается алгоритм yoron^*'

'Костин В.А. и др. Применение трехдиагональных матриц к решению дифференциальных уравнений / Воронеже, ун-т. -Воронеж, 1988. -18 с. -Деп. в ВИНИТИ 12.01.88, JHI5-B88.

представляющий такую модификацию Ш-разложения, в которой на главной диагонали верхней двухдиагональной матрицы и расположены главные минора А., 1=1,п матрицы исходной системы. В диссертации выведены апостериорные оценки точности репгения, служащие основой написания машинно реализуемых процедур вычисления погрешности решения.

Вторая модификация связана с переупорядочением уравнений и неизвестных. Упорядочение строк и столбцов вида 1,3,5,7,...,2,6,10,

14,...,4,12,20,28 ..... 8,24,40,56,..., l-Z4,3-24,5 -2".....(с^ГЮ^,

скобки"f "I" означают "целую часть числа") приводит к алгоритму циклической редукции. Исследование этого алгоритма на устойчивость осуществляется во второй главе.

Третья модификация - использование ш-разлокения "возмущенной" матрицы - рассматривается на примере решения трехдиагональных СЛАУ с постоянными коэффициентами. Исследуются два метода решения системы (I), В которой а =а, b¿=b, с_=о, i=2,...,n-1, о1=о, ап=а - алгоритм I Д.Ивенса, С.Форрингтона и алгоритм 2 А.Ф.Воеводина, Н.Н.Павлова. На основе предложенной матричной интвриретации этих алгоритмов выясняется их связь друг с другом и осуществляется обобщение алгоритма А.Ф.Воеводина, Н.Н.Павлова на случай кусочно-постоянных коэффициентов матрицы исходной системы. Основная идея обоих методов - применение LU-разложения матрицы,- отличавшейся от исходной элементом, находящимся в позиции (1,1). Это разложение удобно тем, что получаемые матрицы Ь и и - с постоянными коэффициентами, тогда как в ш-разложении исходной матрицы ь и и - с переменными коэффициентами и их вычисление осуществляется по рекуррентным соотношениям.

Для того, чтобы найти решение исходной системы, в обоих алгоритмах необходимо решить две системы с одной и той же возмущенной матрицей, например, методом прогонки. Окончательная оценка погрешности (приводится оценка для алгоритма 2) запишется как

п-2 „ ¡.-A n-i+k-1 ^ . ¿-1

|бх _. I < (1 + |х |)e(|pl'|hl 2 ipi + 2 ipi 2 2 |рГ).

n v k=o k=o j=o k=o

Здесь p=oh, (3=ah, h=2/(b + /bz-4ao ).

Для М-матриц при удовлетворении условии (2"') (тем самым, оценки будут справедливы и при условии (2')) имеем I) если о>а, то

1

|Бх I < Б(1 + 1Х41)(1Ы1Р1|(П-1)Н-

1 1-1(31

2) если о<а, то

6(1-451) 16x1 < -Л— (2(п-1}+11г|);

1-1Р1

3) если а=о, то

16x1 < е(1-»-1511 )(|!г| (п-1)+1+(п-а)(п+1-1 )/2).

В третьем параграфе приводится анализ накопления ошибок округления метода ортогональной прогонки для общего случая системы (I) вне зависимости от удовлетворения условиям диагонального преобладания (2)-(2"'). Исходя из соотношений мевду коэффициентами системы (они приведены в тексте диссертации), итоговая погрешность может СЫТЬ:

- ограничена величиной, не зависящей от порядка системы;

- расти с увеличением п не болев, чей линейно;

- иметь квадратичную зависимость погрешностей округления решения от порядка системы;

- изменяться по экспоненциальному закону относительно числа уравнений.

Так, одна из возможных формул 18хп_. I < £твйп(п-±-1),

е - величина, характеризующая машинную точность вычислений, п -число уравнения, У,эе - параметры устойчивости (выраженные через коэффициенты системы), ъ - константа [7].

Во второй главе рассматривается численная устойчивость алгоритмов, допускавдих реализацию на многопроцессорных вычислительных системах.

В первом параграфе приводится общая схема редукции. На этой основе разбираются алгоритмы А.Н.Коновалова и Н.Н.Яненно, циклической редукции, анализируется их численная устойчивость.

В методе "параллельной" прогонки А.Н.Коновалова и Н.Н.Яненко исходная система расщепляется на подсистемы, связанные параметрическими уравнениями. Главной особенностью алгоритма является то, что все получаемые системы имеют вид (I) и решаются методом прогонки.

1

(п-1+и-)+1);

1—I р I

Поэтому при исследовании устойчивости можно воспользоваться его оценками. Однако специальный вид вспомогательных систем позволяет их уточнить. В диссертации приведен перечень полученных неравенств в зависимости от соотношений коэффициентов исходной системы.

Для метода циклической редукции, рассматриваемого как поэтапное исключение каздого второго компонента искомого вектора, отдельно исследуются случаи строгого и нестрогого диагонального преобладания, используемого в виде (2"). При строгом диагональном преобладании справедливо неравенство

14?« ес* 1бзо | < ее,-г <

1-Q

1-Я*

1 1

т>=а- (1+а) < 1, -

° г 1 i 1+а

q= flogen), fl = maxCC,?,"»]}, 1+а, 1+а

< 1, £=maxC-

1+а

1+а.

-} < 1,

а - максимальные значения величины диагонального преобладания в виде (2") для редуцированной системы 1-го уровня.

Для нестрогого диагонального преобладания оценка погрешности решения имеет вид

lös I < ео[ (п+1 )Y'4'1'-nT(log2(л+1 )-1)],

(4)

С - константа, 7 - параметр устойчивости [2], е - величина, характеризующая машинную точность вычисления. В наиболее распространенных и практически важных случаях оценка (4) запишется как

I <еС[(п+1 )4-(п+1 f 2(log, (n+1 M ) ].

Во втором параграфе изучается матричная интерпретация общей схемы редукции. Если it,i2,.произвольный набор индексов, l=ii<i2<...<ilil=n, то при упорядочении строк и столбцов вида

1,2.....12-1,12+1.....1,-1, ia+i, i3+2.....ij-l, i3.....^ система

(I> запишется как

(5)

Aj- блочно-даагональная матрица размерности (n-i+1)«(n-l+1), состо-

< i > < i >

...,А размерности

'vj.?..' V

/V • ь : d . v . V

ящая из 1 трехдиагональных подматриц А

. < 1 > - < 2 >

Ь<1>),и= (и,1,.0,,>.....и<1'),

«Ч = ^ " V ь= № • ь ь'к,,0<к>-подматрицы размерности (1-1 )»п1г и г^* (1-1) соответственно, к=1,...,1, Б - диагональная (1-1)«(1-1)-матрица. Из блочного го-разложения системы (5)

: о

о

£ : Ас

е :А и

• о

о : в

как частные случаи в диссертации выводятся методы А.Н.Коновалова и Н.Н.Яненко, циклической редукции, встречной прогонки и алгоритм тюлои.

В третьем параграфе проводится исследование устойчивости параллельных алгоритмов решения рекурсивных задач на примере метода прогонки. Рекуррентные соотношения составляют основу многих алгоритмов решения СЛАУ. Однако их распараллеливание вызывает немало трудностей. В диссертации рассматривается один из подходов - использование техники сопровождающих функций и множеств. Построение последних и анализ их устойчивости по отношению к накоплении ошибок округления демонстрируется на примере метода прогонки. Для этого выражение первого прогоночного коэффициента р. с помощью вектор-параметра

(¿'"^(1), а'"'^?)) записывается в виде линейной рекурсивной

функции второго порядка, а формулы вычисления второго прогоночного коэффициента ъ^ и решения xi с помощью вектор - параметра в'™=

(в;:;(1 ),ъ'°'1(г))~ в виде линейной рекурсивной функции первого

порядка. Имеют место следующие оценки накопления погрешностей округления

бА*' Ш <

{1 ек

е (0-1) 1

0*1

О = 1

(2РГ-1 Г е- Р ^ 1/г

бв""(1) < { 2Р-1

ак

|5В<к> (2) | < 6

= 1/2 ,

X

В

3=1,2, ¿=1....... к=1 ,...ч=Г1овг11"1.

1а I

Здесь р = тах{|р. I,- },

О, Р - определенные в [з 1 константы, полученные через значения вектор-параметров А*' = (А*к>(1),к[к'(2)), В^' = (В^'т.В^Чг)) соответственно.

В четвертом параграфе рассматривается предлагаемая автором модификация метода Жордана, легко реализуемая на параллельных ЭВМ. В процессе исследования выяснилась тесная связь этой модификации с "распараллеливанием прогонки" с использованием техники сопровождающих функций и множеств. Тем самым получена наглядная иллюстрация, с помощью которой можно легко построить модификацию ЫЬразлокения, лежащую в основе алгоритма "распараллеливания прогонки". Данный алгоритм включает два этапа. На первом осуществляется прямой ход метода Гаусса, в результате насчитываются прогоночные коэффициента" р., 2И причем р. вычисляются рекуррентю, расчет проводится параллельно. Аналогично получению г., на втором этапе двухдиагона-льная система сводится к диагональной. Модификацию можно рассматривать и как метод распараллеливания двухдиагональных систем.

В диссертации приведены формулы, лежащие в основе машинной реализации апостериорной оценки точности решения.

В пятом параграфе изучаются методы, связанные с нахождением обратной матрицы. Во введении к параграфу описываются основные идеи алгоритмов а) основывающихся на правиле Крамера (алгоритм П.Шварц-траубера), б) использующих в своем построении цепные дроби (алгоритм Н.А.Йедашковского), в) алгоритмы обращения матриц (алгоритм Ю.М.Нечепуренко). В параграфе представлен алгоритм А.Н.Остыловского нахождения л'1 и решения СЛАУ по формуле Х=А~1!', приведены формулы, согласно которым осуществляются апостериорные оценки точности решения системы (I) этим методом.

В третьей главе приводится способ построения апостериорных оценок, сравнение числэнной устойчивости изученных алгоритмов, описывается комплекс программ решения трехдиагональных систем с гарантированной точностью вычислений.

В первом параграфе для иллюстрации полученных оценок рассматривается серия методических экспериментов на БЭСЫ-6 и ЕС-1061. В качестве модельных взяты системы разностных уравнений, аппроксими-

рующих простейшие краевые задачи, точное решение которых известно. Результаты экспериментов иллюстрируют:

- ограниченность ошибок округления не зависящей от порядка системы константой в случае строгого диагонального преобладания решения системы (I) методами прогонки, ортогональной прогонки и циклической редукции;

- повышение (на 2-3 порядка) точности вычисления при выборе нужной модификации метода прогонки;

- точность решения групш алгоритмов, для которых диагональное преобладание не играет существенной роли - величина погрешности при решении одной из модельных задач алгоритмом А.Н.Остыловскаго и ортогональной прогонки на 7-8 порядков меньше по сравнению с обычной прогонкой;

- метода решения систем с постоянными коэффициентами;

- исследование различных постановок краевых задач и изучение зависимости погрешности от гладкости решения;

- сравнение предлагаемых оценок с аналогичными интервального анализа.

В этом ге параграфе на основе оценок, полученных в первых двух главах, делаются вывода относительно численной устойчивости изученных алгоритмов, приводятся рекомендации по выбору метода решения и то организации вычислений с целью уменьшения накопления погрешностей округления.

Во втором параграфе поясняется принцип построения алостериор-шх оценок точности решения системы (I). Применяемый аппарат - частично-пооперационный метод наховдения погрешности - позволяет избегать чрезмерных временных затрат и дополнительного расхода операти-яой памяти, возникающих при реализации программ интервального и му подобных анализов, где существенен полностью пооперационный чет ошибок округления.

Для характеристики качества предложенных оценок на примере ме-ода прогонки приведено их сравнение с оценками интервального ана-иза. По точности обе оценки практически совпадают, однако в неко-зрых случаях предлагаемая удобнее в использовании, т.к. во-первых, ремя ее вычисления в несколько раз меньше по сравнению с временем ¿числения интервальной, во-вторых, применение предлагаемой оценки з требует перестройки программа решения задачи.

В третьем параграфе представляется комплекс программ решения трехдиагональных систем линейных уравнений с гарантированной точностью вычислений, специфика которого состоит в том, что помимо решения задачи одним из предложенных методов, можно получить и оценку точности решения. В комплексе собраны 30 подпрограмм, включаюцих

- подпрограммы решения системы (I);

- подпрограммы вычисления гарантированной точности решения;

- иллюстрационные программы.

Программы первой группы являются независимыми, пользователь может выбрать тот из методов, который более удовлетворяет необходимым требованиям. Описание каждого метода снабжено рекомендациями по применению, исследованием точности решения.

В заключении приведены основные результаты диссертации.

В приложении I описываются особенности машинной арифметики, характеризуются подходы к изучению ошибок округления.

На примере метода ортогональной прогонки в приложении 2 демонстрируется техника получения оценок. Кроме того, в нем разработаны 2 частных случая - наличие диагонального преобладания, записанного в виде (2') и (2"').

В приложении 3 собраны: пример оформления программы, листинг подпрограммы, реализующей вычисление апостериорной оценки точности решения, сводная таблица методов.

III. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведен анализ накопления вычислительных погрешностей, возника-пцих при решении на ЭВМ трехдиагональных СЛАУ методами: прогонки и ее модификациями, ортогональной прогонки, циклической редукции, методами "распараллеливания прогонки". Построены априорные и реализуемые на ЭВМ апостериорные оценки точности решения.

2. Предложены матричные интерпретации общей схемы редукции, методов решения систем с постоянными и кусочно-постоянными коэффициентами, алгоритма "распараллеливания прогонки" с использованием техники сопровоадавдих функций.

3. Осуществлено сравнение численной устойчивости прямых методов решения трехдиагональных СЛАУ, выработаны рекомендации по организации вычислений для повышения численной устойчивости. Эффективность предлагаемых модификаций исследована на методических зада-

чах с помощью численных экспериментов, t. Создан комплекс программ решения трехдиагоналышх систем прямыми методами линейной алгебры с нахождением априорной и апостериорной оценки точности вычисленного решения.

IT. ПУБЛИКАЦИИ ПО ТЕ® ДИССЕРТАЦИИ

1. Акимова S.H., Пинкина H.A. Устойчивость и реализация "параллельной" прогонки// Проекционно-сеточные метода в задачах численного анализа. -Новосибирск, 1989. -С. 3-12.

2. Ильин В.П., Кодачигова Л.К., Пинкияа H.A. Анализ устойчивости метода циклической редукции.-Новосибирск,1988.-24 с.-(Препринт/ АН СССР. Сиб. отд-ние. ВЦ; 801).

3. Ильин В.П., Кузнецов И.Б., Пинкина H.A. Исследование устойчивости параллельных алгоритмов решения рекурсивных задач на примере метода прогонки. -Новосибирск, 1989. - 18 с. -(Препринт/АН СССР. Сиб. отд-ние. ВЦ; 841).

4. Ильин В.П., Пинкина H.A. Анализ устойчивости прогонки при решении параболических уравнений//Числ.методы механики сплошной среды / АН СССР. Сиб. отд-ние. Ин-т теорет. и прикл. механики. -1386. -Т.17, 5. -С. 3-18.

5. Ильин В.П., Пинкина H.A. Сравнительный анализ устойчивости методов решения трехдиагоналышх систем уравнений// Тез. докл. 2 Всесоюз. конф.: Новые подходы к решению дифференциальных уравнений, Дрогобнч, июнь 1989. -M.: 1989. -С. 75.

6. Кодачигова Л.К., Пинкина H.A. О численной устойчивости одного метода "распараллеливания" прогонки// Тез. докл. Ш всесоюз. конф. "Однородные вычислительные среды и систолические структуры", Львов, апр. 1990 г. -Львов, 1990. -Т. 3. -С. 79-83.

7. Пинкина H.A. Анализ устойчивости ортогональной прогонки.

Новосибирск, 1989. - 29 с. -(Препринт/АН СССР. Сиб. отд-ние. ВЦ; 871).

3. Пинкина H.A. Машинная реализация вычисления гарантированной точности решения на ЭВМ трехдиагоналышх систем линейных алгебраических уравнений// Вычислительный эксперимент в математической физике. -Новосибирск, 1990. -С. 45-56.

Э. Пинкина H.A. Комплекс программ реиения трехдиагональных систем линейных уравнений с гарантированной точностью

вычислений (Описание применения программы). -Гос. ФАЛ и 50900000903 в Сиб. отд-нии АН СССР. -Новосибирск, -157 с. (ВЦ СО АН СССР).

Ю.Шнкина H.A. Исследование ошибок округления реп трехдаагональных систем линейных уравнений с постоя коэффициектами/7ХХ1 региональная школа-конференция.-Сверд 1990. -С. 27-31.

П.Пинкина H.A. Сравнительный анализ ошибок округления реш систем трехточечных уравнений. -Новосибирск, 1990. Препринт/АН СССР. Сиб. огд-ние. ВЦ; S90).