Рассмотрим систему трехточечных уравнений

(4.44)

и предположим, что коэффициенты и отличны от нуля. Матрица этой системы является трехдиагональной и имеет вид

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

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

(4.45)

с неопределенными коэффициентами и .

Подставим в уравнение .

Получим . После приведения подобных имеем

. (4.46)

Подставим теперь (4.45) в (4.46) и преобразуем полученное равенство

,

.

Последнее уравнение справедливо для любых , если

,

.

Отсюда получаем рекуррентную формулу для

, , (4.47)

и рекуррентную формулу для определения

, . (4.48)

В обоих случаях предполагается, что .

Если коэффициенты и известны и известно значение , то, двигаясь от к , получим последовательно все . Определим начальные значения для коэффициентов и . Для этого используем первое уравнение системы (4.44) и равенство (4.45) при . Имеем

,

.

Сравнивая эти уравнения, получим

, . (4.49)

Используем теперь для определения значения последнее уравнение системы (4.44) и равенство (4.45) при . В результате получим систему уравнений

,

решая которую находим

. (4.50)

Описанный метод решения систем линейных алгебраических уравнений с трехдиагональной матрицей называется методом правой прогонки. Коэффициенты и называются прогоночными коэффициентами, формулы (4.47)-(4.49) описывают прямой ход метода прогонки, а формулы (4.45) и (4.50) – обратный ход. Для решения системы (4.44) необходимо выполнить операций умножения и деления.

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

Теорема 4.5 (достаточное условие корректности и устойчивости метода прогонки). Пусть коэффициенты системы (4.1) удовлетворяют условиям , ,

, , , , ,

, (4.51)

, , (4.52)

причем хотя бы в одном из неравенств (4.51) или (4.52) выполняется строгое неравенство, т. е. Матрица системы (4.44) имеет диагональное преобладание. Тогда для метода прогонки имеют место неравенства , , , гарантирующие корректность и устойчивость метода.

Доказательство: Покажем, что из неравенства , и условий теоремы следует, что и .

Пусть , . Тогда

= .

Следовательно, . Кроме того

.

Так как , то неравенства выполняются для всех . Покажем, что . Если , то и . Значит, если одно из неравенств (4.51) или (4.52) является строгим, то обязательно и

.

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

и следует, что

, т. е. , где и

. Так как для всех , то

.

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

ЛЕКЦИЯ № 16

5. ПОЛНАЯ И ЧАС­ТИЧНАЯ ПРОБЛЕМЫ СОБСТВЕННЫХ ЗНАЧЕНИЙ.

Постановка задачи

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

Собственным значением (или характеристиче­ским числом) квадратной матрицы А называется такое число λ, что для некоторого ненулевого вектора х имеет место равенство

Ах= λ х. (5.0)

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

Условием существования у однородной системы (5.0) ненулевого решения (для наглядности запишем эту систему в виде (А— λ Е)х = 0является требование

|А- λ Е| =

Это уравнение обычно называют вековым (или характеристическим) уравнением матрицы А. Такие уравнения часто встречаются в приложе­ниях. Левая часть векового уравнения

|А- λ Е| = (-1)ⁿ (λⁿ – p₁ λ^n-1- p₂ λ^n-2 - …., - р_п)

носит название характеристического полинома матрицы А. Старший коэффициент этого полинома равен (—1)^п. Иногда вместо характеристи­ческого полинома рассматривают полином, отличающийся от характери­стического множителем (-1)^п. Этот полином

Р( λ )= λⁿ – p₁ λ^n-1- p₂ λ^n-2 - …., - р_п

обычно называют собственным многочленом матрицы. Собственные зна­чения матрицы являются корнями собственного многочлена. Совокуп­ность всех собственных значений λ₁, λг, .... , λ_п матрицы А, где каждое собственное значение выписано столько раз, какова его кратность как корня собственного многочлена, называется спектром этой матрицы. Собственными же векторами матрицы А являются нетривиальные реше­ния однородной системы (5.0), в которой вместо λподставлены соб­ственные значения λ_iматрицы. В том случае, когда для данного собствен­ного значения система (5.0) имеет несколько линейно независимых решений, этому собственному значению принадлежит несколько собст­венных векторов.

Задачу вычисления собственных значений и собственных векторов матрицы А можно разбить на три естественных этапа:

1) строение собственного многочлена Р( λ ) матрицы;

2) решение уравнения Р(λ)=0 и нахождение собственных значе­ний λ_i (i=1, 2,... , п) матрицы;

3) отыскание нетривиальных решений однородных систем (А- λ_i Е)х = 0),(i=1,2.. ,n),

т. е. нахождение собственных векторов матрицы.

Каждый из трех отмеченных этапов решения проблемы собственных значений представляет собой достаточно сложную вычислительную задачу.

В самом деле, построение собственного многочлена Р(λ), например, связано с развертыванием определителя

(-1)ⁿ (λⁿ – p₁ λ^n-1- p₂ λ^n-2 - …., - р_п) = (-1)ⁿ Р(λ),

что представляет собой значительные технические трудности. Основное затруднение вызвано тем обстоятельством, что λвходит в каждую строку и в каждый столбец определителя. В общем же случае, как известно из алгебры, коэффициенты p_i собственного многочлена Р(λ) представляют собой взятые со знаком (-1)^i-1 суммы всех главных миноров (т. е. мино­ров, симметрично расположенных относительно главной диагонали) порядка i определителя матрицы Л. Число таких миноров для каждого i равно числу сочетаний из п по i. Значит, непосредственное вычисление коэффициентов собственного многочлена Р(λ) квадратной матрицы по­рядка п связано с вычислением 2ⁿ -1 определителей различных порядков.

Трудности в непосредственном осуществлении второго и третьего эта­пов решения проблемы собственных значений, т. е. трудности, связанные с решением алгебраических уравнений высоких степеней, и трудности в нахождении нетривиальных решений систем однородных линейных алгебраических уравнений, также значительны. К настоящему времени создано немало специальных вычислительных приемов, упрощающих численное нахождение собственных значений и собственных векторов матрицы. Все эти методы, как и в случае проблемы численного решения системы линейных алгебраических уравнений, мож­но разделить на точные и итерационные методы. К первой группе отно­сятся методы, по которым сначала строят собственный многочлен матри­цы (т. е. вычисляют его коэффициенты р_1, р₂, ... , р_п), затем, находя его корни, получают собственные значения матрицы и уже по ним находят соответствующие собственные векторы. Методы этой группы получили название точных методов в связи с тем обстоятельством, что в случае точного за­дания (рациональными числами) элементов матрицы и при точном (по правилам действий над обыкновенными дробями) проведении вычис­лений такие методы приводят к точным значениям коэффициентов соб­ственного многочлена, а координаты собственных векторов при этом оказываются выраженными через соответствующие собственные зна­чения.

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

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

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

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

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

Пример 1. Найти собственные числа и собственные векторы матрицы A методом непосредственного вычисления определителя (ε = 0.5 · 10^-3 ).

А =

Составим характеристическое уравнение матрицы А, корнями которого являются собственные числа матрицы

|А- λ Е| = = 0.

Непосредственно вычислив определитель третьего поряд­ка, имеем

(2 — λ) (4 — λ)( — 1— λ) —15 — 12 — 9(4 — λ) — 10(2 — λ) — 2( — 1— λ) = 0,

откуда λ ³ — 5 λ ² — 19 λ + 89 = 0. Полученное уравнение ре­шаем методом Ньютона, предварительно отде­лив корни. Находим

f(λ ) = λ ³ — 5 λ ²— 19 λ + 89, f'(λ) = 3 λ ²—10 λ —l9,

следовательно λ₁ =1,2; λ₂ = 4,7.

Составим таблицу знаков функции f(λ )

Как видно из таблицы, уравнение имеет три действи­тельных корня:

λ₁ [- ∞; -1,2]; λ₂ [ - 1,2; 4,7]; λ₃ [4,7; +∞].

Выберем для уточнения один из них, например λ₂. Уменьшим промежуток

[-1,2; 4,7], в кото­ром находится этот корень. Для этого вычислим значе­ния функции f(λ ) в некоторых точках промежутка: f(2) = 39 > 0; f(3) = 14 > 0; f(4)= - 3 < 0. Итак, корень λ₂ содержится внутри промежутка [3; 4]. Уточнение корня производим по формуле

λ_n+1 = λ_n - f(λ_n) / f ^/ (λ_n)/

После уточнения имеем λ₂ ≈ 3,7621. Для определения двух других собственных чисел решаем квадратное урав­нение, полученное при делении многочлена f(λ ) на

λ- 3,7621: λ ²—1б2379 λ — 23,6571 = 0: λ₁ ≈ - 4,2841; λ₃ ≈ 5,5220.

Для определения собственных векторов, соответству­ющих найденным собственным значениям, воспользуем­ся системой линейных уравнений, полученных из ра­венства (А— λ Е)х = 0. При λ₁ ≈ - 4,2841 получим си­стему

6,2841x₁ - x₂ + 3x₃ = 0,

- 2х₁ + 8,2841 х₂ + 5х₃ = 0,

Зх₁ + 2x₂ + 3, 2841x₃ = 0.

Решив ее, получим х⁽¹⁾ = с (- 0,597; - 0,746; 1)^T.

Анало­гично определяются два других собственных вектора.

При λ₂ = 3,7621 имеем

-1,7621x₁ - x₂ + 3x₃ = 0,

- 2х₁ + 0,2379 х₂ + 5х₃ = 0,

Зх₁ + 2x₂ -4,7621x₃ = 0.

х⁽²⁾ = с (1; -0,492; 0,423)^T.

При λ₃= 5,5220 имеем

-3,522x₁ - x₂ + 3x₃ = 0,

- 2х₁ + 1,522 х₂ + 5х₃ = 0,

Зх₁ + 2x₂ - 6,522x₃ = 0.

х⁽³⁾ = с ( - 0,00858; 0,228; 1)^T.

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

Метод А. Н. Крылова

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

D(λ) ≡ det(λ E - A) = λⁿ + p₁ λ^n-1 + p₂ λ^n-2 + …., + р_п (5.1)

— характеристический полином (с точностью до знака) матрицы А. Согласно тождеству Гамильтона — Кели, матрица А обращает в нуль свой характеристический полином; поэтому

Aⁿ + p₁ A^n-1 +…+ p_n E = 0. (5.2)

Возьмем теперь произвольный ненулевойвектор y ⁽⁰⁾ =

Умножая обе части равенства (5.2) справа на y⁽⁰⁾ получим:

Aⁿ y⁽⁰⁾ + p₁ A^n-1 y⁽⁰⁾ +…+ p_n y⁽⁰⁾ = 0. (5.3)

Положим:

A^k y⁽⁰⁾ = y^(k) (k=1, 2, ..., п); (5.4)

тогда равенство (5.3) приобретает вид

y⁽ⁿ⁾ + p₁ y^(n-1) +…+ p_n y⁽⁰⁾ = 0. (5.5)

или (5.5^*)

где

y^(k) = , (k=1, 2, ..., п).

Следовательно, векторное равенство (5.5^*) эквивалентно системе уравнений

p₁ y_j ^(n-1) + p₂ y_j ^(n-2) + …., + р_п y_j⁽⁰⁾ = -y_j⁽ⁿ⁾(j = 1. 2. . . ., n),(5.6)

из которой можно определить неизвестные коэф­фициенты p₁, p_2,....., р_п .

Так как на основании формулы (5.4)

y^(k) =A y ^{(k -1)}, где (k = 1, 2, . . ., п),

то координаты y₁ ^(к) , y₂ ^(к) , …, y_n ^(к) вектора y^(k) последовательно вычисляются по формулам

, ,…, (5.7)

Таким образом, определение коэффициентов p_j характеристи­ческого полинома (5.1) методом А. Н. Крылова сводится к решению линейной системы уравнений (5.6), коэффициенты которой вычи­сляются по формулам (5.7), причем координаты начального вектора

y ⁽⁰⁾ =

произвольны. Если система (6) имеет единственное решение, то ее корни р₁, р₂, ..., р_п являются коэффициентами характеристического полинома (5.1). Это решение может быть найдено, например, методом Гаусса. Если система (5.6) не имеет единственного решения, то задача усложняется . В этом случае рекомендуется изменить начальный вектор.

Пример. Методом А. Н. Крылова найти характеристический полином матрицы

А =

Решение. Выберем начальный вектор y ⁽⁰⁾ = .

Пользуясь формулами (5.7), определим координаты векторов

y^(k) = A^k y⁽⁰⁾ , (k=1, 2, ..., п).

y⁽¹⁾ = A y⁽⁰⁾ = = ; y⁽²⁾ = A y⁽¹⁾ = = ;

y⁽³⁾ = A y⁽²⁾ = = ; y⁽⁴⁾ = A y⁽³⁾ = = ;

Составим систему (6):

которая в нашем случае будет иметь вид

= - .

Отсюда 208p₁ + 30p₂ + p₃ + p₄ = - 2108,

178p₁ + 22p₂ +2p₃ = - 1704,

192p₁ + 18p₂ +3p₃ = - 1656,

242p₁ + 20p₂ +4p₃ = - 1992.

Решив эту систему, получим: р₁ = - 4; р₂ = - 40; р₃ = - 56; р₄ = - 20.

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

det(λ E - A) = λ⁴ - 4 λ³ - 40 λ² - 56 λ – 20.

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

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

ЛЕКЦИЯ № 17

Не нашли, что искали? Воспользуйтесь поиском по сайту: