Processing math: 100%

Критерий обратимости

Теорема (Критерий обратимости квадратных матриц). Квадратная матрица порядка n обратима тогда и только тогда, когда она невырожденная.

Необходимость. Пусть AMn(P). И пусть для нее существует правая обратная матрица, тогда, применяя одно из свойств умножения матриц, получаем AB=E, где Eединичная матрица.det(AB)=detAdetB=1detA0 — по определению матрица A невырожденная.

Тогда покажем, что и для левой обратной матрицы результат аналогичен. Применяя одно из свойств умножения матриц получаем BA=E.det(BA)=detBdetA=1detA0 — по определению матрица A невырожденная.

Зная определение обратной матрицы, видим, что необходимость выполняется.

Достаточность. Пусть AM0n(P), то есть(detA)0. Укажем обратную матрицу явно. Для удобства обозначим за ˜A=(A11A12A1nA21A22A2nAn1An2Ann)- присоединенную матрицу такую, что ˜A=Aij, где Aij — это алгебраические дополнения к элементу aij матрицы A, i=¯1,n и j=¯1,n. Тогда (˜A)T=Aji.

Покажем, что A1=1detA(˜A)T. Для этого следует проверить выполнение таких равенств: A1detA(˜A)T=E и 1detA(˜A)TA=E.

Проверим первое равенство. Положим B=A1detA(˜A)T, тогда bij=nk=1aik1detAAjk=1detAnk=1aikAjk.

Если i=j, то по определению детерминанта получаем bij=1detAdetA=1.

Если ij, то по теореме о «чужих» дополнениях bij=0.

Таким образом, мы доказали, что E=A1detA(˜A)T.

Проверим второе равенство. Положим, C=1detA(˜A)TA. Тогда cij=nk=11detAAjkaik=1detAnk=1Ajkaik. Получаем, что при i=j cij=1detAdetA=1, а при ijcij=0.

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

Следствие. detA1=(detA)1.

Примеры решения задач

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

  1. Докажите, что матрица A не имеет обратной. A=(1021234621230121).
    Решение

    Следуя из условия требуется показать, что исходная матрица не удовлетворяет условиям критерия обратимости квадратных матриц. Проверим матрицу на невырожденность, для этого сначала приведем данную матрицу к треугольному виду методом Гаусса. Получаем A=(1021234621230121)(2346212310210121)(234621230121120121)(234602230121012112)(2346022301210000). Видим, что матрица имеет нулевую строку, по третьему свойству определителей, определитель данной матрицы равен нулю, а это по определению означает, что исходная матрица вырождена. Следовательно, исходная матрица не имеет обратной.

  2. Найти значение выражения (detA)1+3detB1, не вычисляя обратные матрицы, где A=(012037123),B=(102431203).

    Решение

    По следствию из критерия обратимости квадратных матриц получаем detA1+3detB1. Так из лекции обратимость матриц мы знаем, что detA1=1detA.detA=|012037123|=76=1,detB=|102431203|=912=3. Тогда 11+3(13)=11=0.

    Ответ: 0.

Смотрите также

  1. А.Г. Курош. Курс высшей алгебры. М.: Наука, 1965. — 431 с. — С. 95-98.
  2. Конспект Г.С.Белозерова. Глава 4 — 18 с. — С. 11 — 12.
  3. Д.К. Фаддеев. Лекции по алгебре: Учебное пособие для вузов. — М.: Наука, 1984. — 416 с. — С. 134-137.

Критерий обратимости

Пройдите этот тест, чтобы проверить свои знания по прочитанной теме.

Теорема Крамера

Пусть дана система линейных уравнений (СЛАУ) a11x1++a1nxn=b1am1x2++amnxn=bm}, где a11,a1n,am1,amn — числовые коэффициенты, x1,x2,x3 — переменные, b1,bm — свободные члены.

Обозначим матрицу-столбец неизвестных (X), матрицу коэффициентов при неизвестных (A) и столбец правых частей (B): X=x1xn,A=a11a1nam1amn,B=b1bm.

Соотношения, задаваемые системой, запишем в виде матричного уравнения (AX=B): x1xna11a1nam1amn=b1bm.

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

Теорема. Пусть задана СЛАУ от n неизвестных с квадратной невырожденной матрицей над полем P. Тогда общее решение такой системы содержит лишь одно частное решение (x01,x02,,x0n)Pn, которое находится по формуле x0i=ΔiΔ,i=1,,n, где Δопределитель матрицы системы, а Δi — определитель, получаемый из этой матрицы заменой i-го столбца столбцом свободных членов системы.

Докажем теорему, воспользовавшись матричным уравнением AX=B: x1xna11a1nam1amn=b1bm.

Единственность. Пусть имеется решение уравнения X0. Тогда AX0=B. Так как определитель матрицы отличен от нуля можем быть уверены, что существует обратная к A матрица A1. Умножим обе части равенства слева на A1: A1(AX0)=(A1A)X0=EX0=X0=A1B. Следовательно, если решение существует, то оно неизбежно будет равно A1B.

Существование. Сделаем замену: X0=A1B. Подставим в уравнение: A(A1B)=(AA1)B=EB=B. Делаем вывод что, решение существует. Используя явное представление обратной матрицы, можем показать явный вид решения: A1B=Δ1A11An1A1nAnnb1bn=Δ1nj=1Aj1bjnj=1Ajnbj.

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

Алгоритм решения СЛАУ методом Крамера

  1. Находим определитель матрицы искомой системы Δ=|a11a1nam1amn|. Определитель обязательно должен быть отличен от нуля.
  2. Находим определители матриц Δxn=|a11a12b1a21a22b2an1an2bn|, в которых k-ые столбцы (k=1,2,,n) заменены на столбец свободных членов системы.
  3. Вычисляем неизвестные переменные по формуле: xn=ΔxnΔ.
  4. Выполняем проверку решения, подставив xk(k=1,2,,n) в исходную систему. Все уравнения системы должны быть тождественно равны.

Некоторые следствия из теоремы Крамера

Следствие 1. Если определитель матрицы из коэффициентов системы равен нулю и все определители «вспомогательных» (в которых i-ый столбец заменен на столбец свободных членов) матриц равны нулю, то система имеет бесконечное количество решений.

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

Следствие 3. Если определитель матрицы из коэффициентов системы отличен от нуля, то система имеет решение, причём единственное.

Примеры решения задач

  1. Решить систему уравнений методом Крамера {2x1x2x3=43x1+4x22x3=113x12x2+4x3=11
    Решение
  2. Решить систему уравнений методом Крамера {ax3y=12x+ay=2
    Решение
  3. Решить систему уравнений методом Крамера {x1+x2+2x3=12x1x2+2x3=44x1+x2+43=2
    Решение
  4. Найти количество решений у системы уравнений {2x1+3x2x3=34x1+6x22x3=63x1x2+2x3=1
    Решение
  5. Решить систему уравнений методом Крамера {2x1+6x2+4x3=8x1+5x2+4x3=8x1+5x2+7x3=17
    Решение

Тест на знание темы «Теорема Крамера».

Смотрите также

  1. Личный конспект, составленный на основе лекций Белозерова Г.С.
  2. Курош А.Г., Курс высшей алгебры М.: Наука, 1972, 10-ое издание, Глава 1, § 7, «Теорема Крамера» (стр. 53 — 59)
  3. Фадеев Д.К. Лекции по алгебре: Учебное пособие для вузов. — М.: Наука. Главна редакция физико-математической литературы, 1984.-416с. (стр. 106 — 108)
  4. Фадеев Д.К., Соминский И.С. Сборник задач по высшей алгебре М.: Наука, 1972, 10-ое издание, Глава 3, § 1, «Теорема Крамера» (стр. 56)

Алгоритм Горнера

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

    Алгоритм Горнера помогает решать две алгебраические задачи:

  1. Решение уравнений высших степеней;
  2. Работа с многочленами.

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

Выведем схему Горнера

Пусть нам нужно найти корни многочлена P(x), то есть решить уравнение P(x)=0. P(x) представим в виде: ni=0aixi=anxn+an1xn1++ a1x+a0. Решение может осуществляться методами, которые используют производные (если нам нужно найти только действительные корни), а также любыми итерационными способами. Последний требует многократного вычисления значений многочлена.

По следствию из теоремы Безу, многочлен P(x) можно представить в виде: P(x)=(xx0)Q(x)+R(x), где Q(x)  результат деления P(x) на (xx0), R(x)  остаток от этого деления. Обозначим Q(x) как bn1xn1+bn2xn2++b0. Перепишем наш многочлен: anxn+an1xn1++a1x+a0P(x)(xx0)(bn1xn1+bn2xn2++b0)Q(x)+R(x). Для того чтобы вычислить значения многочлена, нам необходимо при заданном x=x0 найти степени xk0, (k=¯1,n), результаты умножить на коэффициенты (bn1,bn2,,b0), а получившееся сложить. Однако, чтобы ускорить процесс и вдвое сократить количество умножений, можно воспользоваться алгоритмом Горнера. Выведем его.

Алгоритм берет свое начало из теоремы Безу, которая звучит так: если многочлен P(x) разделить на двучлен (xx0), то остаток от этого деления будет равен значению P(x) на элементе x0, т.е. (остаток)R(x)=P(x0).

В тождестве (1) умножим (xx0) на Q(x). Получаем anxn+an1xn1++a1x+a0bn1xn+bn2xn1++b0xx0bn1xn1x0bn2xn2x0b0+R(x). Теперь приравняем коэффициенты при одинаковых степенях x: bn1=an; bn2=an1+x0bn1; ; R(x)=a0+x0b0. Приходим к исходному: R(x)=P(x0). Результаты оформим в виде таблицы:

an an1 a0
x0 bn1 bn2 R(x)

Эта таблица и есть схемой Горнера.

Замечание: помимо значения остатка R(x), алгоритм дает нам Q(x) (неполное частное). Также, если остаток R(x)=0, то x0 корень многочлена P(x).

Далее, с помощью примеров, рассмотрим, как алгоритм работает на практике.

Примеры решения задач

  1. Разделить многочлен P5(x)=x58x4+7x34x2+16x+24 на (x2).
    Решение
  2. Определить кратность корня x0=1 многочлена P5(x)=x58x3+14x29x+2.
    Решение
  3. При каких значениях A и B многочлен P4(x)=Ax4+Bx2+1 делится на (x1)2?
    Решение
  4. Дан многочлен P4(x)=x4(2+i)x3(3+2i)x+5 над полем \usepackageamsfontsC. Разделить его с остатком на (xx0), где x0=1i, попутно вычислив P4(x0).
    Решение

Почему алгоритм Горнера работает?

После ознакомления с примерами решения задач, можно приступить к изучению данного вопроса. Представим многочлен уже привычным нам образом P(x)=anxn+an1xn1++a1x+a0. Сделаем самое очевидное действие — вынесем x за скобки: x(anxn1+an1xn2++a1)+a0. Если мы повторим это действие n1 раз, то получим x(x(xn1(anx+an1)+)+a1)+a0. Алгоритм Горнера работает вне зависимости от того, какая степень у многочлена — схема универсальна. Посмотрим на примере. P7(x)=x7+5x62x5x4+3x28x+11==x(x6+5x52x4x3+3x8)+11==x(x(x5+5x42x3x2+3)8)+11==x(x(x(x4+5x32x2x+0)+3)8)+11==x(x(x(x(x3+5x22x1)+0)+3)8)+11==x(x(x(x(x(x2+5x2)1)+0)+3)8)+11==x(x(x(x(x(x(n1)=(71)=6(x+5)2)1)+0)+3)8)+11==x(x(x(x(x(x((1x)+5)2)1)+0)+3)8)+11. Отсюда видим, для того чтобы посчитать выражение (2), мы должны 1 (коэффициент перед x7) умножить на x, результат прибавить к 5 (коэффициент перед x6), опять умножить на x и т.д. То есть мы делаем все то, что и в схеме Горнера.

Почему разложение P(x)=(xx0)Q(x)+R(x) — верно? Начнем с арифметики. Возьмем какое-то натуральное число a. Как гласит нам основная теорема арифметики, его всегда можно представить в виде произведения двух других чисел с остатком, то есть a=sq+r. Например, 7=23+1, 8=42+0. Разложение такого типа единственно, причем 0r<s.

Тоже самое происходит и с многочленами. Допустим, мы хотим разделить многочлен P(x) на Q(x) с остатком. Значит P(x) можно записать как P(x)=S(x)Q(x)+R(x), где 0degR(x)<degQ(x).

Если Q(x)=(xx0) (линейный многочлен), то его степень — единица. Тогда результатом деления любого многочлена на линейный, будет какой-то новый многочлен степени на единицу меньше, и остаток — многочлен нулевой степени (любое число в степени 0  это 1). Следовательно, остатком всегда будет просто число. Именно его мы ищем в схеме Горнера в конце каждой строки.

Дополнительные примеры решения задач

  1. Разложить многочлен P6(x)=x6+6x5+3x428x39x2+54x27 по степеням (x1).
    Решение
  2. Найти все рациональные корни многочлена P7(x)=9x7+3x623x5+4x45x3+23x213x+2.
    Решение

Алгоритм Горнера

Тест на проверку знаний по теме «Алгоритм Горнера»

Смотрите также

  1. Алгебра: Теоремы и алгоритмы: учеб. пособие / Н. И. Яцкин. — Иваново: Иван. гос. ун-т, 2006. — 506с. (c.383-394, 501-503)
  2. Основы численных методов: Учебник для вузов/В.М.Вержбицкий. — М.: Высш. шк., 2002. — 840c. (с.272-275)
  3. Личный конспект, составленный на основе лекций Белозерова Г.С.

Лемма о степени произведения двух многочленов

Лемма. Степень произведения двух многочленов равна сумме степеней множителей.

Рассмотрим многочлены u(x)=anxn+an1xn1++a2x2+a1x+a0, v(x)=bmxm+bm1xm1++b2x2+b1x+b0, p(x)=u(x)v(x)=cn+mxn+m+cn+m1xn+m1++c2x2+c1x+c0. По определению произведения многочленов, коэффициенты p(x) равны ci=α+β=iaαbβ,(i=0,1,,n+m1,n+m). Рассмотрим коэффициент многочлена p(x) при xn+m: cn+m=α+β=n+maαbβ=anbm. Очевидно, anbm0, иначе хоть один из множителей был бы равен нулю и степени u(x) и/или v(x) были бы нарушены. Тогда cn+m0 и deg(p(x))=deg(u(x))+deg(v(x))=n+m.

Примеры решения задач

Читателю предлагается решить эти примеры и сравнить своё решение с приведённым.

  1. Вычислить deg(p(x))=u(x)v(x), если: u(x)=6x819x7+40x652x5+74x460x3+34x2+5x+50, v(x)=42.
    Решение

    Очевидно, умножение на число не изменит степени многочлена. Однако, убедимся в этом с помощью леммы, считая v(x) многочленом нулевой степени. deg(p(x))=deg(u(x))+deg(v(x))=8+0=8.

  2. Определить степень произведения u(x)v(x), если: u(x)=10x7+26x6+46x5+56x4+114x3+80x2+48x+70, v(x)=39x5+185x4+193x3+81x2+56x+20.
    Решение

    Воспользуемся леммой. Пусть p(x)=u(x)v(x). Тогда: deg(p(x))=deg(u(x))+deg(v(x))=7+5=12.

Смотрите также

  1. А.Г. Курош Курс высшей алгебры. — Издание девятое. — Москва:Наука, 1968. — 431с. (c. 132)
  2. Р.Галлагер Теория информации и надежная связь. -М.:»Советское радио», 1974. — 720с. (c. 232-233)
  3. Белозёров Г.С. Конспект лекций.

Лемма о степени произведения двух многочленов

Этот тест призван проверить Ваши знания по теме «Лемма о степени произведения двух многочленов».

Лемма о степени суммы двух многочленов

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

Рассмотрим многочлены u(x)=anxn+an1xn1++a2x2+a1x+a0, v(x)=bmxm+bm1xm1++b2x2+b1x+b0, s(x)=u(x)+v(x)=cpxp+cp1xp1++c2x2+c1x+c0, где p=max(m,n). По определению суммы двух многочленов, коэффициенты s(x) равны ci=ai+bi,(i=0,1,,p1,p). Рассмотрим коэффициент многочлена s(x) при xp: cp=an+bm, если они существуют, т.е. если n=m. Если же n>m, то cp=an. Иначе, n<m и cp=bm. Таким образом, степень s(x) не будет больше max(m,n). В случае же m=n и an=bm, cp=0 и степень s(x)<p.

Примеры решения задач

Читателю предлагается решить эти примеры и сравнить своё решение с приведённым.

  1. Какой степени будет сумма u(x)+v(x), если: u(x)=10x7+26x6+46x5+56x4+114x3+80x2+48x+70, v(x)=7x7+19x6+39x5+185x4+193x3+81x2+56x+20?
    Решение

    Воспользуемся леммой. Пусть s(x)=u(x)+v(x). Поскольку deg(v(x))=deg(u(x))=7, коэффициент многочлена s(x) при x7 равен c7=10+7=170. Следовательно, deg(s(x))=7.

  2. Определить степень суммы многочленов u(x)+v(x), если: u(x)=45x747x6x5140x4+10x3+13x2+24x+12, v(x)=45x7+47x6+x5+27x4+12x3+6x2+2x+21.
    Решение

    Воспользуемся леммой. Пусть s(x)=u(x)+v(x), коэффициенты u(x), v(x), s(x) равны ai, bi, ci соответственно. Аналогично предыдущему случаю, deg(v(x))=deg(u(x))=7. Рассмотрим коэффициенты s(x): c7=a7+b7=45+(45)=0. Значит, deg(s(x))<7. c6=a6+b6=47+47=0, c5=a5+b5=1+1=0, c4=a4+b4=140+27=1130. Значит, deg(s(x))=4.

Смотрите также

  1. А.Г. Курош Курс высшей алгебры. — Издание девятое. — Москва:Наука, 1968. — 431с. (c. 132)
  2. Р.Галлагер Теория информации и надежная связь. -М.:»Советское радио», 1974. — 720с. (c. 232-233)
  3. Белозёров Г.С. Конспект лекций.

Лемма о степени суммы двух многочленов

Этот тест призван проверить Ваши знания по теме «Лемма о степени суммы двух многочленов».