1.3. Основные теоремы

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

Теорема Адамара [1]. Если для матрицы А порядка n выполняется n неравенств

a_kk- >0, ( ), (1.16)

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

Доказательство

Пусть матрица А- вырождена, т.е. detA=0. Тогда существуют такие числа х₁, х₂, …, х_n c максимальным x_k>0, что выполняется

( ).

Также выполняется

a_kkx_k x_jx_k ( ).

Далее сокращая на x_k, получим

a_kk ( )

или a_kk- 0, ( ). Следовательно, при выполнении неравенств (1.16) detA0, т.е. А – невырождена. Теорема доказана.

Теорема о LU разложении [9]. Пусть все главные миноры матрицы А n-го порядка отличны от нуля, то есть

а₁₁0, 0, …, detA0, (1.17)

тогда матрица А представима в виде

A=LU, (1.18)

где L – нижняя треугольная матрица, U – верхняя треугольная матрица.

Доказательство

Доказательство проведем по методу математической индукции. Для n=1 утверждение (1.18) выполняется так как a₁₁=l₁₁u₁₁ .

Тогда пусть теорема верна для матрицы A_n-1 порядка (n-1), т.е.

A_n-1=L_n-1U_n-1 . (1.19)

Покажем, что (1.19) влечет за собой (1.18). Для этого представим матрицу А в следующем виде

А= = , (1.20)

где

А_n-1= , Z= , V= .

Дальше А будем искать в виде (1.18). Тогда имеем

A= = . (1.21)

Из (1.21) получаем

L_n-1U_n-1=A_n-1 , L_n-1Y=Z , XU_n-1=V , XY+l_nnu_nn=a_nn . (1.22)

Первое из уравнений (1.22) выполняется из предположения (1.19). Так как detA_n-10 по условию (1.17), то матрицы L_n-1 и U_n-1 обратимы. Следовательно, из второго и третьего уравнений из (1.22) однозначно определяются вектор-столбец Y и вектор-строка Х.

Таким образом, остается определить только диагональные элементы l_nn и u_nn из четвертого уравнения. Это всегда можно сделать, приписав одному из чисел l_nn , u_nn произвольное и отличное от нуля значение, тогда второе число определится однозначно. Теорема доказана.

Отметим, что эта теорема является типичной теоремой существования, где доказано, что матрица А представима в виде (1.18), но не указан алгоритм построения треугольных матриц L , U.

Теорема 1.1 [7, 9]. Если матрица А имеет только простые собственные значения, то существуют преобразования подобия, приводящие её к диагональной форме.

Доказательство

Расположим n – линейно независимые собственные вектора матрицы А в столбцах матрицы Т

Т= . Тогда

АТ=А = =

= =Т.

Т^-1АТ=. Теорема доказана.

Отметим, что преобразование Т^-1АТ называется преобразованием подобия.

Теорема 1.2 [9]. Пусть detA0, тогда матрица А разлагается в произведение

A=QR, (1.23)

где Q – ортогональная матрица, R – верхняя треугольная матрица.

Доказательство

Для доказательства необходимо найти такое преобразование, которое ортогонализирует столбы матрицы А. Пусть a_i – столбцы матрицы А. Так как detA0, то система векторов a_i являются линейно независимой и образует базис в пространстве Rⁿ.

Тогда отыскание нужного преобразования сводится к задаче об ортогонализации базиса. Ортогональный базис будем строить с помощью алгоритма Грама-Шмита.

Пусть Q=(q₁, q₂,…, q_n) – искомая матрица с ортогональными столбцами q_i.

Положим a₁=q₁. Далее вектор а₂ разложим по ортогональным векторам q₁, q₂:

a₂=r₁₂q₁+q₂ , (q₁, q₂)=0, r₁₂=( q₁, a₂)/ (q₁, q₁).

Затем вектор а₃ разложим по ортогональным векторам q₁, q₂, q₃:

a₃=r₁₃q₁+ r₂₃q₂+q₃, (q₁, q₃)=0, (q₂, q₃)=0, r₁₃=(q₁, a₃)/(q₁, q₁), r₂₃=(q₂, a₃)/(q₂, q₂) и т.д.

Окончательно, получим

a_i=r_1iq₁+ r_2iq₂+…+r_i-1,iq_i-1+q_i . (1.24)

Коэффициенты разложения (1.24) определяются из условий ортогональности (q_i, q_j)=0 при ij :

r_ij=(q_i, a_j)/(q_i, q_i), i<j.

Матричная запись (1.24) будет

A=Q =QR. Теорема доказана.

Для нахождения векторов q_i из (1.24) получим

q_i=a_i-r_1iq₁-r_2iq₂-…-r_i-1,Iq_i-1.

Теорема 1.3 [9]. Пусть detA0, тогда матрица А разлагается в произведение

A=QL,

где Q – ортогональная матрица, L – нижняя треугольная матрица.

Доказательство

Теорема доказывается аналогично теореме 1.2.