Определение.

Назовем систему системой с диагональным преобладанием по строке, если элементы матрицы удовлетворяют неравенствам:

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

Теорема

Система с диагональным преобладанием всегда разрешима и притом единственным образом.

Рассмотрим соответствующую однородную систему:

Предположим, что она имеет нетривиальное решение , Пусть наибольшая по модулю компонента этого решения соответствует индексу
, т. е.

,
,
.

Запишем -ое уравнение системы в виде

и возьмем модуль от обеих частей этого равенства. В результате получим:

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

Последнее из них означает, что доказательство теоремы завершено.

Системы с трехдиагональной матрицей. Метод прогонки.

При решении многих задач приходится иметь дело с системами линейных уравнений вида:

,
,

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

;
,

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

Пользуясь тем, что значения изаданы, перепишем систему в виде:

Матрица этой системы имеет трёхдиагональную структуру:

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

Метод основан на предположении, что искомые неизвестные и
связаны рекуррентным соотношением

,
.

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

Для реализации описанной программы выразим с помощью соотношения
через
:

и подставим
и, выраженные через
, в исходные уравнения. В результате получим:

Последние соотношения будут заведомо выполняться и притом независимо от решения, если потребовать, чтобы при
имели место равенства:

Отсюда следуют рекуррентные соотношения для прогоночных коэффициентов:

,
,
.

Левое граничное условие
и соотношение
непротиворечивы, если положить

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

Отсюда можно найти остальные неизвестные
в процессе обратной прогонки с помощью рекуррентной формулы.

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

Во многих прикладных задачах, которые приводят к СЛАУ с трехдиагональной матрицей, ее коэффициенты удовлетворяют неравенствам:

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

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

Лемма

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

Доказательство проведем по индукции. Согласно
, т. е. при
утверждение леммы верно. Допустим теперь, что оно верно дляи рассмотрим
:

Итак, индукция от к
обоснована, что и завершает доказательство леммы.

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

НЕВЫРОЖДЕННОСТЬ МАТРИЦ И СВОЙСТВО ДИАГОНАЛЬНОГО ПРЕОБЛАДАНИЯ1

Цветкович Лилиана - профессор, кафедра математики и информатики, факультет науки, Университет Нови Сад, Сербия, Обрадовича 4, Нови Сад, Сербия, 21000, e-mail: [email protected].

Костич Владимир - ассистент профессора, доктор, кафедра математики и информатики, факультет науки, Университет Нови Сад, Сербия, Обрадовича 4, 21000, Нови Сад, Сербия, email: [email protected].

Крукиер Лев Абрамович - доктор физико-математических наук, профессор, заведующий кафедрой высокопроизводительных вычислений и информационно-коммуникационных технологий, директор Южно-Российского регионального центра информатизации Южного федерального университета, пр. Стачки 200/1, корп. 2, г. Ростов-на-Дону, 344090, e-mail: krukier@sfedu. ru.

Cvetkovic Ljiljana - Professor, Department of Mathematics and Informatics, Faculty of Science, University of Novi Sad, Serbia, D. Obradovica 4, Novi Sad, Serbia, 21000, e-mail: [email protected].

Kostic Vladimir - Assistant Professor, Department of Mathematics and Informatics, Faculty of Science, University of Novi Sad, Serbia, D. Obradovica 4, Novi Sad, Serbia, 21000, e-mail: [email protected].

Krukier Lev Abramovich - Doctor of Physical and Mathematical Science, Professor, Head of the Department of High Performance Computing and Information and Communication Technologies, Director of the Computer Center of the Southern Federal University, Stachki Ave, 200/1, bild. 2, Rostov-on-Don, Russia, 344090, e-mail: krukier@sfedu. ru.

Диагональное преобладание в матрице является простым условием, обеспечивающим ее невырожденность. Свойства матриц, которые обобщают понятие диагонального преобладания, всегда очень востребованы. Они рассматриваются как условия типа диагонального преобладания и помогают определять подклассы матриц (типа H-матриц), которые при этих условиях остаются невырожденными. В данной работе строятся новые классы невырожденных матриц, которые сохраняют преимущества диагонального преобладания, но остаются вне класса H-матриц. Эти свойства особенно удобны, поскольку многие приложения приводят к матрицам из этого класса, и теория невырожденности матриц, которые не являются Н-матрицами, теперь может быть расширена.

Ключевые слова: диагональное преобладание, невырожденность, масштабирование.

While simple conditions that ensure nonsingularity of matrices are always very welcomed, many of which that can be considered as a type of diagonal dominance tend to produce subclasses of a well known H-matrices. In this paper we construct a new classes of nonsingular matrices which keep the usefulness of diagonal dominance, but stand in a general relationship with the class of H-matrices. This property is especially favorable, since many applications that arise from H-matrix theory can now be extended.

Keywords: diagonal dominance, nonsingularity, scaling technique.

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

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

Теорема 1. Пусть дана матрица A = е Cnxn такая, что

ы > г (a):= S k l, (1)

для всех i е N:= {1,2,...n}.

Тогда матрица А является невырожденной.

Матрицы, обладающие свойством (1), называются матрицами со строгим диагональным преобладанием

(8ББ-матрицами). Их естественным обобщением является класс матриц с обобщенным диагональным преобладанием (вББ), определенный следующим образом:

Определение 1. Матрица А = [а^ ] е Спхп называется вББ-матрицей, если существует невырожденная диагональная матрица W такая, что AW является 8ББ-матрицей.

Введем несколько определений для матрицы

А = [ау ] е Спхп.

Определение 2. Матрица (А) = [тук ], определен-

(A) = е Cn

называется матрицей сравнения матрицы А.

Определение 3. Матрица A = е C

\üj > 0, i = j

ется M-матрицей, если

aj < 0, i * j,

обратная мат-

рица А" >0, т.е. все ее элементы положительны.

Очевидно, что матрицы из класса вББ также являются невырожденными матрицами и могут быть

1Работа частично поддержана Министерством образования и науки Сербии, грант 174019, и Министерством по науке и технологическому развитию Воеводины, гранты 2675 и 01850.

найдены в литературе под названием невырожденных Н-матриц . Их можно определить с помощью следующего необходимого и достаточного условия:

Теорема 2. Матрица А = [ау ]е сихи является Н-

матрицей тогда и только тогда, когда ее матрица сравнения является невырожденной М-матрицей.

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

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

Рассмотрим матрицу А = [ау ] е спхп и индекс

Введем матрицу

r (A):= £ a R (A):= £

ßk (A) := £ и yk (A) := aü - ^

Легко проверить, что элементы матрицы Ьк АЬк имеют следующую форму:

ßk (A), У k (A), akj,

i = j = k, i = j * k,

i = k, j * k, i * k, j = k,

A inöaeüiüö neö^äyö.

Если применить теорему 1 к описанной выше матрице Ьк АЬк1 и ее транспонированной, то получим две основные теоремы.

Теорема 3. Пусть дана любая матрица

А = [ау ] е спхп с ненулевыми диагональными элементами. Если существует к е N такое, что > Гк (А), и для каждого г е N \ {к} ,

то матрица А является невырожденной.

Теорема 4. Пусть дана любая матрица

А = [ау ] е спхп с ненулевыми диагональными элементами. Если существует к е N такое, что > Як (А), и для каждого г е N \ {к},

То матрица А является невырожденной. Возникает естественный вопрос о связи между

матрицами из предыдущих двух теорем: Ь^ - БОО -матрицами (определенными формулой (5)) и

Ьк - БОО -матрицами (определенными формулой (6)) и классом Н-матриц. Следующий простой пример проясняет это.

Пример. Рассмотрим следующие 4 матрицы:

и рассмотрим матрицу Ьк АЬк, к е N, подобную исходной А. Найдем условия, когда эта матрица будет обладать свойством SDD-матрицы (по строкам либо по столбцам).

Всюду в статье для г,к еN:= {1,2,.../?} будем использовать обозначения:

2 2 1 1 3 -1 1 1 1

" 2 11 -1 2 1 1 2 3

2 1 1 1 2 -1 1 1 5

Теоремы о невырожденности

Все они являются невырожденными:

А1 является Ь - БОО, несмотря на то, что не является Ьк - БОО для любого к = {1,2,3}. Она также не Н-матрица, поскольку (А^ 1 не является неотрицательной;

А2 благодаря симметрии является одновременно ЬЯ - БОО и Ь<2 - БОО, так же как ЬЯ - БОО и

Ь<3 - БОО, но не является Н-матрицей, так как (А2) вырожденная;

А3 является Ь9 - БОО, но не является ни

Lr - SDD (для k = {1,2,3}), ни Н-матрицей, поскольку (A3 ^ - также вырожденная;

A4 является Н-матрицей, так как (A^ невырожденная, и ^A4) 1 > 0, хотя она не является ни LR - SDD , ни Lk - SDD для любого k = {1,2,3}.

Рисунок показывает общую связь между

Lr - SDD , Lk - SDD и Н-матрицами вместе с матрицами из предыдущего примера.

Связь между lR - SDD, lC - SDD и

ад min(|au - r (A)|) "

Начиная с неравенства

и применяя данный результат к матрице Ьк АЬ ^, получаем

Теорема 5. Пусть дана произвольная матрица А = [а-- ] е Спхп с ненулевыми диагональными эле-

ментами. Если А принадлежит классу - БОО, тогда

1 + max^ i*к \акк\

Н-матрицами

Интересно отметить, что хотя мы и получили

класс ЬСк БОО -матриц путем применения теоремы 1 к матрице, полученной транспонированием матрицы Ьк АЬ^1, данный класс не совпадает с классом, полученным посредством применения теоремы 2 к матрице Ат.

Введем определения.

Определение 4. Матрица А называется { Ьк -БОО по строкам}, если АТ { Ьк-БОО }.

Определение 5. Матрица А называется { ЬСк -БОО по строкам}, если АТ { ЬСк -БОО }.

Примеры показывают, что классы Щ - БОО,

ЬС-БОО, { Ьк - БОО по строкам} и { Ь^-БОО по строкам} связаны друг с другом. Таким образом, мы расширили класс Н-матриц четырьмя разными способами.

Применение новых теорем

Проиллюстрируем полезность новых результатов при оценке С-нормы обратной матрицы.

Для произвольной матрицы А со строгим диагональным преобладанием широко известная теорема Вараха (УагаИ) дает оценку

min[|pf (A)| - тк (A), min(|yk (A)| - qk(A) - |af (A)|)]" i i (фf ii ii

Аналогичным образом получаем следующий результат для матриц Lk - SDD по столбцам.

Теорема 6. Пусть дана произвольная матрица A = е сихи с ненулевыми диагональными элементами. Если A принадлежит классу Ьк -SDD по столбцам, тогда

Ik-lll <_ie#|akk|_

" " mln[|pf (A)| - Rf (AT), mln(|уk (A)|- qk (AT)- |aft |)]"

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

Литература

Levy L. Sur le possibilité du l"equlibre electrique C. R. Acad. Paris, 1881. Vol. 93. P. 706-708.

Horn R.A., Johnson C.R. Matrix Analysis. Cambridge, 1994. Varga R.S. Gersgorin and His Circles // Springer Series in Computational Mathematics. 2004. Vol. 36. 226 р. Berman A., Plemons R.J. Nonnegative Matrices in the Mathematical Sciences. SIAM Series Classics in Applied Mathematics. 1994. Vol. 9. 340 р.

Cvetkovic Lj. H-matrix theory vs. eigenvalue localization // Numer. Algor. 2006. Vol. 42. P. 229-245. Cvetkovic Lj., Kostic V., Kovacevic M., Szulc T. Further results on H-matrices and their Schur complements // Appl. Math. Comput. 1982. P. 506-510.

Varah J.M. A lower bound for the smallest value of a matrix // Linear Algebra Appl. 1975. Vol. 11. P. 3-5.

Поступила в редакцию

$A_{nn}$ обладает свойством диагонального преобладания , если

$|a_{ii}| \geqslant \sum_{j \neq i} |a_{ij}|,\qquad i = 1, \dots, n,$

причём хотя бы одно неравенство является строгим. Если все неравенства строгие, то говорят, что матрица $A_{nn}$ обладает строгим диагональным преобладанием.

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

Свойства

Матрица со строгим диагональным преобладанием является невырожденной .

См. также

Напишите отзыв о статье "Диагональное преобладание"

Отрывок, характеризующий Диагональное преобладание

Гусарский Павлоградский полк стоял в двух милях от Браунау. Эскадрон, в котором юнкером служил Николай Ростов, расположен был в немецкой деревне Зальценек. Эскадронному командиру, ротмистру Денисову, известному всей кавалерийской дивизии под именем Васьки Денисова, была отведена лучшая квартира в деревне. Юнкер Ростов с тех самых пор, как он догнал полк в Польше, жил вместе с эскадронным командиром.
11 октября, в тот самый день, когда в главной квартире всё было поднято на ноги известием о поражении Мака, в штабе эскадрона походная жизнь спокойно шла по старому. Денисов, проигравший всю ночь в карты, еще не приходил домой, когда Ростов, рано утром, верхом, вернулся с фуражировки. Ростов в юнкерском мундире подъехал к крыльцу, толконув лошадь, гибким, молодым жестом скинул ногу, постоял на стремени, как будто не желая расстаться с лошадью, наконец, спрыгнул и крикнул вестового.

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет прикладной математики – процессов управления

А. П. ИВАНОВ

ПРАКТИКУМ ПО ЧИСЛЕННЫМ МЕТОДАМ

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

Методические указания

Санкт-Петербург

ГЛАВА 1. ВСПОМОГАТЕЛЬНЫЕ СВЕДЕНИЯ

В методическом пособии приведены классификация методов решения СЛАУ и алгоритмы их применения. Методы приведены в форме, позволяющей их использование без обращения к другим источникам. Предполагается, что матрица системы неособая, т.е. det A 6= 0.

§1. Нормы векторов и матриц

Напомним, что линейное пространство Ω элементов x называется нормированным, если в нём введена функция k · kΩ , определённая для всех элементов пространства Ω и удовлетворяющая условиям:

1. kxk Ω ≥ 0, причём kxkΩ = 0 x = 0Ω ;

2. kλxk Ω = |λ| · kxkΩ ;

3. kx + yk Ω ≤ kxkΩ + kykΩ .

Договоримся в дальнейшем обозначать малыми латинскими буквами векторы, причём будем считать их вектор-столбцами, большими латинскими буквами обозначим матрицы, а греческими буквами станем обозначать скалярные величины (сохраняя за буквами i, j, k, l, m, n обозначения для целых чисел).

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


	\|xi \|;
1. kxk1 =	\|xi \|;

2. kxk2 = u x2 ; t

3. kxk∞ = maxi |xi |.

Отметим, что все нормы в пространстве Rn являются эквивалентными, т.е. любые две нормы kxki и kxkj связаны соотношениями:

αij kxkj ≤ kxki ≤ βij kxkj ,

k k ≤ k k ≤ ˜ k k

α˜ ij x i x j β ij x i,

причём αij , βij , α˜ij , βij не зависят от x. Более того, в конечномерном пространстве любые две нормы являются эквивалентными.

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

Отмечая подчинённые нормы матриц теми же индексами, что и соответствующие нормы векторов, можно установить, что

k k1

|aij |; kAk2

k∞

(AT A);

Здесь через λi (AT A) обозначено собственное число матрицы AT A, где AT – матрица, транспонированная к A. Кроме отмеченных выше трёх основных свойств нормы, отметим здесь ещё два:

kABk ≤ kAk · kBk,

kAxk ≤ kAk · kxk,

причём в последнем неравенстве матричная норма подчинена соответствующей векторной норме. Договоримся использовать в дальнейшем только нормы матриц, подчинённые нормам векторов. Отметим, что для таких норм справедливо равенство: если E – единичная матрица, то kEk = 1, .

§2. Матрицы с диагональным преобладанием

Определение 2.1. Матрица A с элементами {aij }n i,j=1 называется матрицей с диагональным преобладанием (величины δ) , если имеют место неравенства

|aii | − |aij | ≥ δ > 0, i = 1, n .

§3. Положительно определённые матрицы

Определение 3.1. Симметричную матрицу A будем называть по-

ложительно определённой, если квадратичная форма xT Ax с этой матрицей принимает лишь положительные значения при любом векторе x 6= 0.

Критерием положительной определённости матрицы может служить положительность её собственных чисел или положительность её главных миноров.

§4. Число обусловленности СЛАУ

При решении любой задачи, как известно, имеют место три типа погрешностей: неустранимая погрешность, методическая погрешность и погрешность округления. Рассмотрим влияние неустранимой погрешности исходных данных на решение СЛАУ, пренебрегая погрешностью округления и принимая во внимание отсутствие методической погрешности.

матрица A известна точно, а правая часть b содержит неустранимую погрешность δb.

Тогда для относительной погрешности решения kδxk/kxk

	нетрудно получить оценку:

где ν(A) = kAkkA−1 k.

Число ν(A) называется числом обусловленности системы (4.1) (или матрицы A). Оказывается, что всегда ν(A) ≥ 1 для любой матрицы A. Поскольку величина числа обусловленности зависит от выбора матричной нормы, то при выборе конкретной нормы будем соответственно индексировать и ν(A) : ν1 (A), ν2 (A) или ν∞ (A).

В случае ν(A) 1 систему (4.1) или матрицу A называют плохо обусловленной. В этом случае, как это следует из оценки

(4.2) , погрешность решения системы (4.1) может оказаться неприемлемо большой. Понятие приемлемости или неприемлемости погрешности определяется постановкой задачи.

Для матрицы с диагональным преобладанием легко получить оценку её числа обусловленности сверху. Имеет место

Теорема 4.1. Пусть A – матрица с диагональным преобладанием величины δ > 0. Тогда она неособая и ν∞ (A) ≤ kAk∞ /δ.

§5. Пример плохо обусловленной системы.

Рассмотрим СЛАУ (4.1) , в которой

−1

− 1 . . .

−1

.. .

−1

Данная система имеет единственное решение x = (0, 0, . . . , 0, 1)T . Пусть правая часть системы содержит погрешность δb = (0, 0, . . . , 0, ε), ε > 0. Тогда

δxn = ε, δxn−1 = ε, δxn−2 = 2 ε, δxn−k = 2 k−1 ε, . . . , δx1 = 2 n−2 ε.

k∞ =

2 n−2 ε,

k∞

k k∞

Следовательно,

ν∞ (A) ≥ kδxk ∞ : kδbk ∞ = 2n−2 . kxk ∞ kbk ∞

Поскольку kAk∞ = n, то kA−1 k∞ ≥ n−1 2 n−2 , хотя det(A−1 ) = (det A)−1 = 1. Пусть, например, n = 102. Тогда ν(A) ≥ 2100 > 1030 . При этом если даже ε = 10−15 получим kδxk∞ > 1015 . И тем не

Определение.