A_G_2014

следовательно, функции F (x) и F0(x) = (A(x −xˆ), x −xˆ) отличаются на постоянное слагаемое. Поскольку матрица A положительно определена, то единственной точкой минимума функции F0, а стало быть, и функции F является xˆ. Вследствие (2.15) неравенство (2.12) можно записать в виде

Таким образом, можно сказать, что при выполнении условий теоремы 3 итерационный процесс (2.3) является релаксационным2): каждое последующее приближение уменьшает значение функционала F .

6. Используя полученные в предыдущем пункте общие результаты, исследуем сходимость метода релаксации (2.2).

6.1. Теорема. Пусть матрица A положительно определена,

Тогда итерационный метод (2.2) сходится при любом начальном приближении x0.

Доказательство. Будем опираться на теорему 3. В рассматриваемом случае B = D + ωL, τ = ω, B1 = D + (ω/2)(L + L ), A = D+L+L , и условие (2.9) принимает вид (Dx, x) > (ω/2)(Dx, x) для любого x ≠ 0. Все диагональные элементы положительно определенной матрицы положительны (см. упражнение 3 на с. 224), поэтому матрица D положительно определена, и условие (2.9) выполнено, если выполнено условие (2.17).

6.2. Теорема. Условие (2.17) необходимо для сходимости итерационного процесса (1.9).

Доказательство. Запишем равенство (2.7) в виде

Поскольку L и R — строго треугольные матрицы, а D — диагональная матрица, все диагональные элементы которой отличны от нуля, то, вычисляя определители левой и правой частей равенства (2.18), получим, что det(S) = (1 − ω)n, следовательно (см. (7.7), с. 193),

∏n

k=1

2)Релаксация (лат. relaxatio) — уменьшение напряжения, ослабление.

где λ1, λ2, . . . ,λn — характеристические числа матрицы S. Если условие (2.17) нарушено, то |1 − ω| > 1, и среди собственных чисел λk матрицы S есть хотя бы одно, модуль которого больше единицы, но тогда по теореме 2 найдется начальное приближение x0, при котором итерационный процесс (1.9) не сходится.

7. Пример решения задачи об оптимальном выборе итерационного параметра. Из доказательства теоремы 2 видно, что итерационный процесс (2.3) сходится тем быстрее, чем меньше спектральный радиус матрицы S = I −τB−1A. В связи с этим возникает задача отыскания такого (оптимального) значения итерационного параметра τ, при котором величина ρ(S) принимает минимальное значение.

Наиболее просто эта задача решается в случае, когда матрицы A, B положительно определены. Поскольку в рассматриваемом случае B = B , т. е. в представлении (2.10) матрица B2 равна нулю, то из (2.11) получаем, что для любой собственной пары λ, x матри-

Нетрудно видеть, что если x — собственный вектор матрицы S, то x — собственный вектор матрицы B−1A и, следовательно (см. § 13, с. 238), x — собственный вектор обобщенной проблемы собственных значений

Очевидно, справедливо и обратное: любой собственный вектор задачи (2.21) есть собственный вектор оператора S.

Для любой собственной пары x, λ задачи (2.21) справедливо равенство (Ax, x) = λ(Bx, x). Поэтому все собственные числа задачи (2.21) положительны. Пусть m — минимальное, а M максимальное из этих чисел. Тогда для любого собственного вектора x оператора S справедливы неравенства

Полученные оценки являются точными, поскольку соответствующие неравенства (2.22) превращаются в равенства, если в качестве x взять собственный вектор, отвечающий m или M.

Нетрудно видеть, что функция g(µ) = |1 − τµ| вещественного переменного µ на любом ограниченном отрезке вещественной оси достигает максимального значения на одном из концов этого отрезка. Поэтому, используя соотношения (2.20), (2.22), получаем, что

где τ0 = 2/(M + m), ξ = m/M.

Таким образом, итерационный процесс (2.3) при оптимальном значении итерационного параметра τ = τ0 сходится тем быстрее, чем больше m/M, т. е. чем меньше разброс собственных чисел задачи (2.21).

§3. Метод Якоби решения задач на собственные значения

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

Всамых общих чертах, идея его состоит в следующем. Пусть A — диагональная матрица. Тогда собственные числа матрицы A есть ее

диагональные элементы. Метод Якоби для любой эрмитовой матри-

цы A дает способ построения последовательности матриц A1, A2, . . . , Ak, . . . таких, что каждая из матриц этой последовательности эрмитова, подобна матрице A и с увеличением номера k становится все более близкой к диагональной. В качестве приближенных значений собственных чисел матрицы A берутся диагональные элементы мат-

рицы Ak, как только все ее внедиагональные элементы оказываются достаточно малыми.

1. Итак, пусть A — эрмитова матрица порядка n, Q = {qij}ni,j=1 — матрица, отличающаяся от единичной лишь четырьмя элементами:

314 Глава 17. Итерационные методы

где 1 6 k < l 6 n, φ — вещественное число, q — вообще говоря, комплексное число, |q| = 1. Очевидно, Q — унитарная матрица.

Образуем по матрице A матрицу A = QT AQ и попытаемся вы-

Вычислим сумму квадратов модулей внедиагональных элементов

Определим теперь числа k, l из условия:

̸

Поскольку A — эрмитова матрица, то alk = a¯kl, и из (3.5) с учетом того, что 1/q¯ = q, будем иметь, что

Будем считать, что akl ≠ 0. В противном случае матрица диагональна, и ее собственные числа определяются тривиальным образом. Положим

При указанном выборе параметров, определяющих матрицу Q, сумма

b

квадратов модулей внедиагональных элементов матрицы A принимает наименьшее значение.

Теперь можно описать метод Якоби. Пусть A0 = A. Образуем последовательность матриц A1, A2, . . . при помощи рекуррентной формулы:

где параметры матрицы Qp определяются так, чтобы сделать сумму квадратов внедиагональных элементов матрицы Ap+1 минимально возможной, т. е. по формулам вида (3.7), (3.8), (3.10).

Вычисления проводят до тех пор, пока все внедиагональные элементы матрицы Ap не станут достаточно малыми. Тогда в качестве приближений к собственным числам матрицы A принимают диагональные элементы матрицы Ap, а столбцы матрицы Q0Q1 · · · Qp считают приближениями к собственным векторам матрицы A.

§4. Исследование сходимости метода Якоби

1.Лемма. Пусть параметры матрицы Q определяются согласно формулам (3.7), (3.8), (3.10). Тогда

где

2

0 < ρ = 1 − n(n − 1) < 1

при n > 2.

Доказательство. Вследствие (3.10) из (3.6) получаем

316 Глава 17. Итерационные методы

i≠j

Здесь учтено, что матрица порядка n имеет n2 − n внедиагональных элементов. Из (4.2), (4.3) очевидным образом следует (4.1).

Это означает, что по любому заданному ε > 0 можно указать целое положительное число p такое, что

Обозначим через Λp диагональную матрицу, на диагонали которой расположены диагональные элементы матрицы Ap. В соответствии с оценками (4.4), а также (11.4), с. 233, можем написать:

|λk(Ap) − λ(kp)| 6 ε, k = 1, 2, . . . , n,

где λ(kp), k = 1, . . . , n, — диагональные элементы матрицы Λp, упорядоченные по неубыванию, λk(Ap) — так же упорядоченные собственные числа матрицы Ap. Вследствие (3.11) имеем Ap = TpT ATp, где Tp = Q0Q1 . . . Qp, т. е. матрицы Ap и A подобны, а, значит, их собственные числа совпадают, поэтому

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

2. Применяя метод Якоби для приближенного отыскания собственных чисел и собственных векторов симметричной вещественной матрицы, в формулах (3.1) параметр q следует положить равным единице. Соответственно, в формуле (3.10), нужно заменить |akl| на akl. Все выше полученные оценки при этом сохраняются. Матрица Q, определенная на с. 313, при q = 1 есть матрица, осуществляющая поворот на угол φ в двумерной плоскости, натянутой на векторы ik, il естественного базиса пространства Rn. Поэтому метод Якоби часто называют методом вращений.

Глава 18

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

§1. Основные неравенства

1.Вещественная функция f вещественной переменной называ-

ется выпуклой на интервале (a, b), если для любых точек x1, x2 из этого интервала и для любого t [0, 1] выполнено неравенство

Геометрически это означает, что любая точка графика функции f на отрезке [x1, x2] лежит ниже хорды, стягивающей точки (x1, f(x1)), (x2, f(x2)), или на этой же хорде.

2. Теорема. Пусть функция f непрерывна и дважды непрерывно дифференцируема на интервале (a, b), вторая производная f неотрицательна на интервале (a, b). Тогда f — выпуклая функция на интервале (a, b).

Доказательство. В соответствии с определением выпуклой функции нужно установить, что при любых x1, x2 (a, b) функция φ вещественной переменной t, задаваемая равенством

φ(t) = f(tx1 + (1 − t)x2) − tf(x1) − (1 − t)f(x2)

неположительна для всех t из отрезка [0, 1]. Нетрудно видеть, что

φ(0) = 0, φ(1) = 0, φ′′(t) = f′′(tx1 + (1 − t)x2)(x1 − x2)2 > 0

для всех t [0, 1] Пусть t — произвольным образом фиксированная точка из интервала (0, 1). Используя формулу конечных приращений Лагранжа, получим φ(t) = φ(t) − φ(0) = tφ′(t1), где t1 — некоторая точка из интервала (0, t). Аналогично, φ(t) = −(1 − t)φ′(t2), где t2 — точка из интервала (t, 1). Отсюда, очевидно, следует, что φ(t) = −t(1 −t)(φ′(t2) −φ′(t1)). Вновь применяя формулу Лагранжа, получим, что φ(t) = −t(1 − t)(t2 − t1)φ′′(t3), где t3 (t2, t1). Таким образом, φ(t) 6 0.

3. При помощи теоремы 2 легко доказывается, что функция − ln(x) выпукла на интервале (0, ∞). Поэтому для любых положительных чисел a, b и любых p, q > 1 и таких, что 1/p + 1/q = 1,

ln(ap/p + bq/q) > ln(ap)/p + ln(bq)/q = ln(ab),

откуда, учитывая равенство 1 − 1/q = 1/p, получим (1.4).

§2. Нормы на пространстве Cn

1.В этом и последующем параграфах мы будем широко ис-

пользовать понятие сходимости последовательности векторов из пространства Cn, введенное в § 1, гл. 17.

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

ции n комплексных переменных. При этом, аналогично случаю функции, определенной на Rn (см. курс математического анализа), функция f называется непрерывной в точке x Cn, если из сходимости последовательности {xk} к x вытекает сходимость f(xk) к f(x).

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

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

2. Наряду с введенным выше понятием длины (или модуля) вектора x Cn во многих случаях оказывается удобным использовать более общее понятие, а именно, понятие нормы вектора.

Будем говорить, что на пространстве Cn введена норма, если каждому вектору x Cn однозначно поставлено в соответствие вещественное число x (читается: норма x). При этом должны быть выполнены следующие условия (аксиомы нормы):

1)x > 0 для любого x Cn, равенства x = 0 и x = 0 эквивалентны;

2)αx = |α|x для любых x Cn, α C;

3)x + y 6 x + y для любых x, y Cn.

Условие 3) обычно называют неравенством треугольника.

Отметим неравенство

x = x − y + y 6 x − y + y .

Аналогично,

y 6 x − y + x .

Неравенство 4) есть просто более краткая запись этих неравенств.

3. Приведем примеры норм на пространстве Cn.

неравенство 3) при p = 1 непосредственно вытекает из свойств модуля, а при p > 1 совпадает с неравенством Минковского (1.4). Отметим, что x 2 = |x| = (x, x), для любого x Cn, здесь и далее в

этой главе (·, ·) — стандартное скалярное произведение на пространстве Cn.

2) Положим x ∞ = max |xk|. Элементарно проверяется, что это

16k6n

равенство определяет норму.

3) Пусть A — эрмитова положительно определенная матрица. Функция x A = (Ax, x)1/2 есть норма на пространстве Cn. Для обоснования этого факта достаточно вспомнить, что соотношение (x, y)A = (Ax, y) определяет скалярное произведение на пространстве Cn (см. упражнение 1, с. 224, а также п. 3, с. 132).