1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (826648), страница 19

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

Текст из файла (страница 19)

. . , n, т. е.λ(A) ∈n n[i=1oPz ∈ C |z − aii | ≤|a|.j6=i ijС.А. Гершгорин (СССР), 1931 годКруги ГершгоринаОпределениеДля квадратной n × n-матрицы A = (aPij ) круги комплекснойплоскости с центрами aii и радиусами j6=i |aij |, i = 1, 2, . . . , n,т. е. множестваnoPz ∈ C |z − aii | ≤ j6=i |aij | ,i = 1, 2, . . . , n,называются кругами Гершгорина.Круги ГершгоринаОпределениеДля квадратной n × n-матрицы A = (aPij ) круги комплекснойплоскости с центрами aii и радиусами j6=i |aij |, i = 1, 2, . . .

, n,т. е. множестваnoPz ∈ C |z − aii | ≤ j6=i |aij | ,i = 1, 2, . . . , n,называются кругами Гершгорина.Пример. Для матрицы!1 23 4√собственные значения суть 12 (5 ± 33),они приблизительно равны −0.372 и 5.372.Im2-20246Re-2На рисунке, показывающем круги Гершгорина для матрицы,её собственные значения выделены крестиками.Im2-20246Re-2Матрица1 2−3 4!имеет те же самыекруги Гершгорина. Но её собственные значения√равны 21 (5 ± i 15), т. е.

≈ 2.5 ± 1.936 i . Они выделены на рисункезвёздочками и целиком находятся в одном из кругов Гершгорина.Для доказательства теоремы Гершгоринанапомним факты, которые мы изучали:ОпределениеКвадратную n×n-матрицу A = (aij ) называют матрицейс диагональным преобладанием, если для любого i = 1, 2, . . .

, nимеет местоX|aii | >|aij |.j6=iПризнак Адамара неособенности матрицКвадратная матрица с диагональным преобладанием неособенна.Покажем, что теорема Гершгорина равносильнапризнаку Адамара неособенности матриц.Покажем, что теорема Гершгорина равносильнапризнаку Адамара неособенности матриц.Импликация «⇒»В самом деле, пусть матрица имеет диагональное преобладание.Тогда её круги Гершгорина не захватывают начала координат(точки 0) комплексной плоскости C.Поэтому матрица не может иметь нулевое собстенное значение.Следовательно, матрица должна быть неособенной.Импликация «⇐»Пусть верен признак Адамара.Импликация «⇐»Пусть верен признак Адамара.Если λ — собственное значение матрицы A = (aij ), то матрица(A − λI) особенна и потому не может иметь диагональноепреобладание.Импликация «⇐»Пусть верен признак Адамара.Если λ — собственное значение матрицы A = (aij ), то матрица(A − λI) особенна и потому не может иметь диагональноепреобладание.Как следствие, хотя бы для одного i = 1, 2, .

. . , n должно бытьвыполненоX|λ − aii | ≤|aij |,j6=iт. е. λ должно лежать в каком-то (хотя бы одном)круге Гершгорина.Импликация «⇐»Пусть верен признак Адамара.Если λ — собственное значение матрицы A = (aij ), то матрица(A − λI) особенна и потому не может иметь диагональноепреобладание.Как следствие, хотя бы для одного i = 1, 2, . . . , n должно бытьвыполненоX|λ − aii | ≤|aij |,j6=iт.

е. λ должно лежать в каком-то (хотя бы одном)круге Гершгорина.Мы не знаем точного номера i этого круга. Но λ наверняка лежитв объединении всех кругов, с номерами i = 1, 2 . . . , n.Потому в целом получаем утверждение теоремы Гершгорина.Уточнение теоремы ГершгоринаТеоремаЕсли объединение кругов Гершгорина распадается на несколькосвязных частей, которые не пересекаются между собой, то каждаятакая часть содержит столько собственных значений матрицы,сколько кругов её составляют.Вычислительные методыанализа и линейной алгебрыКурс лекцийС.П.

ШарыйКафедра математического моделирования НГУЛекция 15 декабря 2017 г.Итерационный метод ЯкобиПусть в системе линейных алгебраических уравнений Ax = bдиагональные элементы матрицы A = (aij ) отличны от нуля,т. е.aii 6= 0,i = 1, 2, . . . , n.Итерационный метод ЯкобиПусть в системе линейных алгебраических уравнений Ax = bдиагональные элементы матрицы A = (aij ) отличны от нуля,т. е.aii 6= 0,i = 1, 2, .

. . , n.Это условие нисколько не ограничит общность наших рассуждений.В неособенной квадратной матрице A, det A 6= 0, в каждом столбцеи в каждой строке должны стоять ненулевые элементы.Как следствие, с помощью перестановки строк (соответствующейперестановке уравнений системы) всегда можно сделатьдиагональные элементы ненулевыми.В развёрнутом виде система линейных алгебраических уравненийAx = bпредставляется какnXj=1aij xj = bi ,i = 1, 2, . . . , n.В развёрнутом виде система линейных алгебраических уравненийAx = bпредставляется какnXaij xj = bi ,i = 1, 2, .

. . , n.j=1Выражая i-ю компоненту вектора неизвестных из i-го уравнения,получимX1 aij xj  ,bi −i = 1, 2, . . . , n.xi =aiij6=iПолученные соотношения дают представление исходной системылинейных уравнений в рекуррентном видеx = T (x),который необходим для организации одношаговых итерацийx(k+1) ← T (x(k) ),k = 0, 1, 2, . . . .Полученные соотношения дают представление исходной системылинейных уравнений в рекуррентном видеx = T (x),который необходим для организации одношаговых итерацийx(k+1) ← T (x(k) ),ЗдесьT (x) =иTi (x) =k = 0, 1, 2, . .

. .⊤T1 (x), T2 (x), . . . , Tn (x)1 bi −aiiXj6=iaij xj  ,i = 1, 2, . . . , n.Итерационный метод Якобиk ← 0;выбираем начальное приближение x(0) ;DO WHILE ( метод не сошёлся )DO FOR i = 1 TO nX1 (k)(k+1)bi −aij xj xi←aiij6=iEND DOk ← k + 1;END DOВспомогательная переменная k — счётчик числа итераций.Итерационный метод Якоби— предложен ещё в середине XIX века К.Г. Якоби (C.G.Jacobi)и часто (особенно в старых книгах по численным методам)называется «методом одновременных смещений».«Смещения» здесь — это коррекции компонент очередногоприближения к решению, выполняемые на каждой итерации.Смещения-коррекции «одновременны» потому, что все компонентыследующего приближения x(k+1) насчитываются независимо другот друга по формулам, использующим только x(k) .Итерационный метод Якоби— предложен ещё в середине XIX века К.Г.

Якоби (C.G.Jacobi)и часто (особенно в старых книгах по численным методам)называется «методом одновременных смещений».«Смещения» здесь — это коррекции компонент очередногоприближения к решению, выполняемые на каждой итерации.Смещения-коррекции «одновременны» потому, что все компонентыследующего приближения x(k+1) насчитываются независимо другот друга по формулам, использующим только x(k) .Далее мы рассмотрим итерационный процесс, в которомсмещения-коррекции компонент очередного приближения«не одновременны» и находятся последовательно одна из другой.Пусть A = L̃ + D + Ũ , где0 a210...L̃ =  a31 a32 ... ......0an1 an2 · · · an,n−1 00— диагональ матрицы A,D = diag {a11 , a22 , . . . , ann }Ũ = 0 a12 · · · a1,n−1...

a2,n−10......00— строго нижняятреугольная матрица,a1nan−1,n0a2n...— строго верхняятреугольная матрица.Тогда итерационный метод Якоби может быть представлен какметод, основанный на таком расщеплении матрицы системыA = G − H, чтоG = D,H = −(L̃ + Ũ ).Соответственно, в матричном виде метод Якоби записывается какx(k+1) ← −D −1 (L̃ + Ũ ) x(k) + D −1 b,k = 0, 1, 2, .

. . .Тогда итерационный метод Якоби может быть представлен какметод, основанный на таком расщеплении матрицы системыA = G − H, чтоG = D,H = −(L̃ + Ũ ).Соответственно, в матричном виде метод Якоби записывается какx(k+1) ← −D −1 (L̃ + Ũ ) x(k) + D −1 b,k = 0, 1, 2, . . . .Нетрудно дать условия его сходимости, основываясь на общемрезультате о сходимости стационарных одношаговых итераций:метод Якоби сходится из любого начальногоприближения тогда и только тогда, когдаρ D −1 (L̃ + Ũ ) < 1.Матрица D −1 (L̃ + Ũ ) просто выписывается по исходной системе иимеет вид0a12 /a11 · · · a1n /a11 a /a0· · · a2n /a22  21 22.............an1 /ann an2 /ann · · ·0Матрица D −1 (L̃ + Ũ ) просто выписывается по исходной системе иимеет вид0a12 /a11 · · · a1n /a11 a /a0· · · a2n /a22  21 22.............an1 /ann an2 /ann · · ·0Но нахождение спектрального радиуса этой матрицы являетсязадачей, которая сравнима по сложности с выполнением самогоитерационного процесса.Этот способ исследования метода Якоби непрактичен.Матрица D −1 (L̃ + Ũ ) просто выписывается по исходной системе иимеет вид0a12 /a11 · · · a1n /a11 a /a0· · · a2n /a22  21 22.............an1 /ann an2 /ann · · ·0Но нахождение спектрального радиуса этой матрицы являетсязадачей, которая сравнима по сложности с выполнением самогоитерационного процесса.Этот способ исследования метода Якоби непрактичен.Для быстрой и грубой оценки спектрального радиуса можновоспользоваться какой-нибудь матричной нормой и тем фактом,что она не меньше спектрального радиуса.Итерационный метод ЯкобиПолезен следующий достаточный признак сходимости:ТеоремаЕсли в системе линейных алгебраических уравнений Ax = bматрица A — квадратная и имеет диагональное преобладание,то метод Якоби для решения этой системы сходится при любомначальном приближении.Доказательство.Диагональное преобладание в матрице A = (aij ) означает, что|aii | >Xj6=i|aij |,i = 1, 2, .

. . , n.Доказательство.Диагональное преобладание в матрице A = (aij ) означает, что|aii | >X|aij |,i = 1, 2, . . . , n.j6=iСледовательно,X aij < 1, aii i = 1, 2, . . . , n,j6=iчто равносильноmax1≤i≤nX aij aii j6=i!< 1.max1≤i≤nX aij aii j6=i!< 1.Выражение, стоящее в левой части неравенства,является ∞-нормой матрицы D −1 (L̃ + Ũ ), которая имеет вид0 a21 /a22...a12 /a11...a1n /a110........a2n /a22 .....an1 /ann an2 /ann . . .0X aij aii max1≤i≤nj6=i!< 1.Выражение, стоящее в левой части неравенства,является ∞-нормой матрицы D −1 (L̃ + Ũ ), которая имеет вид0a12 /a11...a1n /a110........a2n /a22 .... a21 /a22....an1 /ann an2 /ann .

Характеристики

Список файлов лекций