Рубрика: Алгебра

Учебные материалы по уневерситетскому курсу алгебры

Ранг матрицы

Пусть задана матрица $$\begin{equation*}
A = \left(
\begin{array}{cccc}
a_{11} & a_{12} & \ldots & a_{1n}\\
a_{21} & a_{22} & \ldots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{m1} & a_{m2} & \ldots & a_{mn}
\end{array}
\right)
\end{equation*}, $$ где $n$ столбцов и $m$ строк. Заметим, что числа не имеют никакой связи между собой. Будем рассматривать столбцы как вектора $m-$мерного пространства. То есть в таком виде: $$ \alpha_1 = \left(a_{11}, a_{21},\dots,a_{m1}\right),$$ $$\alpha_2 = \left(a_{12}, a_{22},\dots,a_{m2}\right),$$ $$\vdots$$ $$\alpha_m = \left(a_{1n}, a_{2n},\dots,a_{mn}\right).$$ Они могут быть линейно зависимыми. Тогда имеет место такое определение:

Определение. Пусть задана матрица $A = \|a_{ij}\| \in M_{m \times n}(P).$
Рангом матрицы называется ранг системы её столбцов, то есть количество векторов (столбцов) в максимально линейно независимой системе столбцов матрицы $A.$ Обозначение: $\mathop{\rm rank} A.$

Примечание. Ранг нулевой матрицы равен нулю.
$$\left(\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{matrix} \right).$$ Как видим, столбцы равны между собой, а значит линейно независимые столбцы отсутствуют, их количество равно нулю и, по определению, ранг равен нулю.

Ранг системы столбцов также можно называть «столбцовым» рангом. Очевидно, для строк существует аналогичное название — «строчный» ранг. Однако в этом случае строки будут рассматриваться как вектора $n-$мерного пространства, а именно: $$ \beta_1 = \left(a_{11}, a_{12},\dots,a_{1n}\right),$$ $$\beta_2 = \left(a_{21}, a_{22},\dots,a_{2n}\right),$$ $$\vdots$$ $$\beta_n = \left(a_{m1}, a_{m2},\dots,a_{mn}\right).$$ Ранги равны между собой, что следует из теоремы о ранге матрицы. Необходимо упомянуть, что $\mathop{\rm rank} A \leqslant min\left\{n,m\right\}$, где $n$ — количество столбцов матрицы $A$, а $m$ — количество строк. Этот факт также следует из теоремы.

Пример. Найти ранг матрицы $$A = \left(\begin{array}{rrr} -1 & 3 & 2 & 5 & 12 & -6 \\ 5 & 4 & -1 & -25 & 16 & 3 \\ 2 & 0 & 3 & -10 & 0 & 9 \end{array} \right).$$Запишем столбцы как вектора и проверим есть ли зависимость: $$ \alpha_1 = \left(-1,5,2\right),~ \alpha_2 = \left(3, 4, 0\right),~ \alpha_3 = \left(2,-1,3\right), $$ $$\alpha_4 = \left(5,-25,-10\right),~ \alpha_5 = \left(12,16,0\right),~ \alpha_6 = \left(-6,3,9\right).$$ В нашем случае она очевидна: $$\alpha_4 =-5 \cdot \alpha_1,~ \alpha_5 = 4 \cdot \alpha_2,~ \alpha_6 =-3 \cdot \alpha_3.$$ Значит, линейно независимых столбцов в матрице три и, по определению, $\mathop{\rm rank} A = 3. $

Пример. Найти ранг матрицы $$A = \left(\begin{array}{rrr} 1 & 2 & -4 & 0 \\ -3 & 6 & 7 & 8 \\ -2 & -4 & 8 & 0\end{array} \right).$$ Ранг столбцов равен $4.$ Но это превышает ранг матрицы, который должен быть не больше трех. Узнаем, с помощью элементарных преобразований, есть ли среди строк линейно зависимые: $$\left(\begin{array}{rrr} 1 & 2 & -4 & 0 \\ -3 & 6 & 7 & 8 \\ -2 & -4 & 8 & 0\end{array} \right) \thicksim \left(\begin{array}{rrr} 1 & 2 & -4 & 0 \\ 0 & 11 & -5 & 8 \\ 0 & 0 & 0 & 0\end{array} \right) \thicksim \left(\begin{array}{rrr} 1 & 2 & -4 & 0 \\ 0 & 11 & -5 & 8 \end{array} \right).$$Линейно независимых строк две. Позже будет доказано, что «строчный» ранг равен рангу матрицы. А так как нам известен ранг строк, можно сказать, что $\mathop{\rm rank} A = 2.$

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

  1. Курош А.Г. Курс высшей алгебры М.: Наука, 1968, стр. 71
  2. Александров П.С. Курс аналитической геометрии и линейной алгебры — 2009 стр. 346
  3. Личный конспект, составленный на основе лекций Белозерова Г.С.

Скалярное произведение векторов, свойства, координатное представление

Определение 1. Пусть заданы два ненулевых вектора $a$ и $b$, число, равное произведению длин этих векторов на косинус угла между ними, назовем их скалярным произведением. $$\left( a,b \right) = \left|a\right|\left|b\right|\cos\angle\left(a,b\right)$$ В случае, если хотя бы один из векторов нулевой, будем считать их скалярное произведение равным нулю.

Также существуют другие определения скалярного произведения векторов.

Определение 2. Пусть заданы два ненулевых вектора, число, равное произведению длины первого и величины проекции второго вектора на первый, назовем их скалярным произведением. $$\left( a,b \right) = \left|a\right|\left\{pr_{a}b\right\}$$

Определение 3. Пусть два произвольных вектора заданы своими координатами, число, равное сумме произведений соответствующих координат, назовем скалярным произведением этих векторов.

Докажем эквивалентность первого и второго определений, эквивалентность третьему будет доказана позднее.

Лемма. Первое и второе определения эквивалентны, т.е. $$\left( a,b \right) = \left|a\right|\left|b\right|\cos\angle\left(a,b\right) = \left|a\right|\left\{pr_{a}b\right\}.$$

Воспользуемся определением проекции вектора на ось (другой вектор), откуда получим, что $\left\{pr_{a}b\right\} = \left|b\right|\cos\angle\left(a,b\right)$. Домножив обе части полученного равенства на $\left|a\right|$ получим искомое равенство.

Алгебраические свойства

  1. $\left( a,b \right) = \left( b,a \right)$ (коммутативность).

    Если хотя бы один вектор нулевой, то равенство достигается по определению. Рассмотрим случай ненулевых векторов:$$\left( a,b \right) = \left|a\right|\left|b\right|\cos\angle\left(a,b\right).$$ Умножение коммутативно, следовательно $\left|a\right|\left|b\right| = \left|b\right|\left|a\right|$. Также $\cos\angle\left(a,b\right) = \cos\angle\left(b,a\right)$. Тогда, по определению: $$\left( a,b \right) = \left|a\right|\left|b\right|\cos\angle\left(a,b\right) = \left|b\right|\left|a\right|\cos\angle\left(b,a\right) = \left( b,a \right).$$

    Следствие. $\left( a,b \right) = \left|a\right|\left\{pr_{a}b\right\} = \left|b\right|\left\{pr_{b}a\right\}$.

  2. $\left(\lambda a,b \right) = \lambda\left( a,b \right)$, $\forall\lambda\in\mathbb{R}$.

    Если один из векторов нулевой или $\lambda = 0$, то доказательство очевидно. Рассмотрим общий случай: $$\left(\lambda a,b \right) = \left|\lambda a\right|\left|b\right|\cos\angle\left(\lambda a,b\right),$$ если $\lambda > 0$, то $$\left|\lambda a\right|\left|b\right|\cos\angle\left(\lambda a,b\right) = \lambda\left|a\right|\left|b\right|\cos\angle\left( a,b\right) = \lambda\left(a,b\right),$$ если $\lambda < 0$, то $$\left|\lambda a\right|\left|b\right|\cos\angle\left(\lambda a,b\right) = -\lambda\left|a\right|\left|b\right|\left(-\cos\angle\left( a,b\right)\right) = \lambda\left(a,b\right).$$

    Следствие. $\left(a,\lambda b\right) = \left(\lambda b, a\right) = \lambda\left(b, a\right)$.

  3. $\left(a+c,b\right) = \left(a,b\right)+\left(c,b\right)$.

    Воспользуемся вторым определением и свойствами величины проекции вектора. $$\left(a+c,b\right) = \left|b\right|\left\{pr_{b}\left(a+c\right)\right\} = \left|b\right|\left(\left\{pr_{b}a\right\}+\left\{pr_{b}c\right\}\right) =$$ $$= \left|b\right|\left\{pr_{b}a\right\} + \left|b\right|\left\{pr_{b}c\right\} = \left(b,a\right) + \left(b,c\right) = \left(a,b\right) +\left(c,b\right).$$

  4. $\left(a,a\right)\geqslant 0$, если $\left(a,a\right)=0 \Leftrightarrow a = 0$

    Если $a=0$ доказательство очевидно. Пусть $a\neq0$, тогда $\cos\angle\left(a,a\right) = 1$, следовательно: $$\left(a,a\right) = \left|a\right|\left|a\right|\cos\angle\left(a,a\right) = \left|a\right|\left|a\right| = \left|a\right|^{2}\geqslant 0.$$

    Следствие. $\left|a\right|=\sqrt{\left(a,a\right)}$.

Теорема (неравенство Коши-Буняковского). Пусть заданы векторы $a$ и $b$, тогда выполняется неравенство: $$\left|\left(a,b\right)\right|\leqslant \left|a\right|\left|b\right|$$

Сначала рассмотрим случай равенства: $$\left|\left(a,b\right)\right| = \left|a\right|\left|b\right|,$$ $$\left|\left(a,b\right)\right| — \left|a\right|\left|b\right| = 0,$$ $$ \left|a\right|\left|b\right|\left(\cos\angle\left(a,b\right) — 1\right) = 0,$$ $$\left[
\begin{array}{1 1} \left|a\right| = 0, \\\left|b\right| = 0, \\\left|\cos\angle\left(a,b\right)\right| = 1 \Rightarrow a\|b.\end{array}\right. $$Таким образом равенство достигается в случае коллинеарных или нулевых векторов. Теперь рассмотрим общий случай. Пусть даны два ненулевых вектора $a$ и $b$, тогда $$\left|\cos\angle\left(a,b\right)\right|\leqslant 1,$$ домножим обе части на длины векторов $$\left|a\right|\left|b\right|\left|\cos\angle\left(a,b\right)\right|\leqslant \left|a\right|\left|b\right|,$$ $$\left|\left|a\right|\left|b\right|\cos\angle\left(a,b\right)\right|\leqslant \left|a\right|\left|b\right|,$$ $$\left|\left(a,b\right)\right|\leqslant \left|a\right|\left|b\right|.$$

Геометрические свойства

Рассмотрим геометрические свойства скалярного произведения двух ненулевых векторов, тогда $\left|a\right|\neq 0$ и $\left|b\right|\neq 0$.

  1. $\left(a,b\right)>0 \Leftrightarrow \angle\left(a,b\right)$ — острый.

    $\left(a,b\right)>0 \Leftrightarrow \left|a\right|\left|b\right|\cos\angle\left(a,b\right)>0 \Leftrightarrow \cos\angle\left(a,b\right)>0 \Leftrightarrow \angle\left(a,b\right)$ — острый

  2. $\left(a,b\right)<0 \Leftrightarrow \angle\left(a,b\right)$ — тупой.

    $\left(a,b\right)<0 \Leftrightarrow \left|a\right|\left|b\right|\cos\angle\left(a,b\right)<0 \Leftrightarrow \cos\angle\left(a,b\right)<0 \Leftrightarrow \angle\left(a,b\right)$ — тупой

  3. $\left(a,b\right)=0 \Leftrightarrow \angle\left(a,b\right)$ — прямой, $a\perp b$.

    $\left(a,b\right)=0 \Leftrightarrow \left|a\right|\left|b\right|\cos\angle\left(a,b\right)=0 \Leftrightarrow \cos\angle\left(a,b\right)=0 \Leftrightarrow \angle\left(a,b\right)$ — прямой, $a \perp b$.

Также из определения вытекает формула для нахождения косинуса угла между векторами: $$\cos\angle\left(a,b\right) = \frac{\left(a,b\right)}{\left|a\right|\left|b\right|}$$

Скалярное произведение в координатах

Теорема. Пусть два вектора заданы своими координатами, тогда их скалярное произведение равно сумме произведений соответствующих координат: $$a=\left(x_{1},y_{1},z_{1}\right), b=\left(x_{2},y_{2},z_{2}\right),$$ $$\left(a,b\right) = x_{1}x_{2}+y_{1}y_{2}+z_{1}z_{2}.$$

Рассмотрим два способа доказательства:

I способ

Пусть $a=\left(x_{1},y_{1},z_{1}\right), b=\left(x_{2},y_{2},z_{2}\right)$, отложим векторы $\overline{\rm OA} = a$ и $\overline{\rm OB} = b$ от начала координат — точки $O\left(0,0,0\right)$. Тогда: $$\left( a,b \right) = \left|a\right|\left|b\right|\cos\angle\left(a,b\right) = \left|\overline{\rm OA}\right|\left|\overline{\rm OB}\right|\cos\angle\left(\overline{\rm OA},\overline{\rm OB}\right).$$

Vectors

По построению: $$A\left(x_{1},y_{1},z_{1}\right), \left|a\right|=\left|\overline{\rm OA}\right| = \sqrt{x_{1}^2+y_{1}^2+z_{1}^2},$$ $$B\left(x_{2},y_{2},z_{2}\right), \left|a\right|=\left|\overline{\rm OB}\right| = \sqrt{x_{2}^2+y_{2}^2+z_{2}^2}.$$ Теперь необходимо найти $\cos\angle\left(a,b\right) = \cos\angle\left(\overline{\rm OA},\overline{\rm OB}\right)$, для этого воспользуемся теоремой косинусов для $\angle\left(\overline{\rm OA},\overline{\rm OB}\right) = \angle AOB $: $$\cos\angle AOB = \frac{\left|\overline{\rm OA}\right|^2 + \left|\overline{\rm OB}\right|^2 — \left|\overline{\rm AB}\right|^2}{2\left|\overline{\rm OA}\right|\left|\overline{\rm OB}\right|},$$ где $\left|\overline{\rm AB}\right|=\sqrt{\left(x_{1}-x_{2}\right)^2+\left(y_{1}-y_{2}\right)^2+\left(z_{1}-z_{2}\right)^2}$.

Теперь найдем скалярное произведение: $$\left( a,b \right)=\left|\overline{\rm OA}\right|\left|\overline{\rm OB}\right|\cos\angle AOB=\left|\overline{\rm OA}\right|\left|\overline{\rm OB}\right|\frac{\left|\overline{\rm OA}\right|^2+\left|\overline{\rm OB}\right|^2-\left|\overline{\rm AB}\right|^2}{2\left|\overline{\rm OA}\right|\left|\overline{\rm OB}\right|} = $$ $$= \frac{\left|\overline{\rm OA}\right|^2+\left|\overline{\rm OB}\right|^2-\left|\overline{\rm AB}\right|^2}{2}=$$ $$=\frac{x_{1}^2+y_{1}^2+z_{1}^2+x_{2}^2+y_{2}^2+z_{2}^2-\left(x_{1}-x_{2}\right)^2-\left(y_{1}-y_{2}\right)^2-\left(z_{1}-z_{2}\right)^2}{2} = $$ $$=\frac{x_{1}^2+y_{1}^2+z_{1}^2+x_{2}^2+y_{2}^2+z_{2}^2-x_{1}^2+2x_{1}x_{2}-x_{2}^2-y_{1}^2+2y_{1}y_{2}-y_{2}^2-z_{1}^2+2z_{1}z_{2}-z_{2}^2}{2}=$$ $$=\frac{2x_{1}x_{2}+2y_{1}y_{2}+2z_{1}z_{2}}{2}=x_{1}x_{2}+y_{1}y_{2}+z_{1}z_{2}.$$

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

II способ

Пусть система координат задана единичными взаимно перпендикулярными векторами $i,j,k$ (базисные векторы), тогда $$\left|i\right|=\left|j\right|=\left|k\right|=1,$$ $$\left(i,j\right)=\left(i,k\right)=\left(j,k\right)=0,$$ $$\left(i,i\right)=\left(j,j\right)=\left(k,k\right)=1.$$ А векторы $a=\left(x_{1},y_{1},z_{1}\right), b=\left(x_{2},y_{2},z_{2}\right),$ можно представить в виде сумм: $$a = x_{1}i+y_{1}j+z_{1}k,$$ $$b = x_{2}i+y_{2}j+z_{2}k.$$

Теперь воспользуемся алгебраическими свойствами скалярного произведения: $$\left(a,b\right)=\left(x_{1}i+y_{1}j+z_{1}k,x_{2}i+y_{2}j+z_{2}k\right)=$$ $$= x_{1}\left(i,x_{2}i+y_{2}j+z_{2}k\right) + y_{1}\left(j,x_{2}i+y_{2}j+z_{2}k\right) + z_{1}\left(k,x_{2}i+y_{2}j+z_{2}k\right)=$$ $$= x_{1}x_{2}\left(i,i\right)+x_{1}y_{2}\left(i,j\right)+x_{1}z_{2}\left(i,k\right)+y_{1}x_{2}\left(j,i\right)+y_{1}y_{2}\left(j,j\right)+y_{1}z_{2}\left(j,k\right)+$$ $$+ z_{1}x_{2}\left(k,i\right)+z_{1}y_{2}\left(k,j\right)+z_{1}z_{2}\left(k,k\right)=x_{1}x_{2}+y_{1}y_{2}+z_{1}z_{2}.$$

Следствие. Для ненулевых векторов $a=\left(x_{1},y_{1},z_{1}\right), b=\left(x_{2},y_{2},z_{2}\right)$ $$\cos\angle\left(a,b\right) = \frac{x_{1}x_{2}+y_{1}y_{2}+z_{1}z_{2}}{\sqrt{x_{1}^2+y_{1}^2+z_{1}^2}\sqrt{x_{2}^2+y_{2}^2+z_{2}^2}}.$$

Следствие. Пусть $a=\left(x_{1},y_{1},z_{1}\right), b=\left(x_{2},y_{2},z_{2}\right)$, $$a \perp b \Leftrightarrow x_{1}x_{2}+y_{1}y_{2}+z_{1}z_{2} = 0$$

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

  1. Даны векторы $a=\left(2,5,-1\right)$ и $b=\left(3,2,15\right)$. Найти скалярное произведение $\left(a,b\right)$.
    Решение

    Воспользуемся определением через координаты, тогда: $$\left(a,b\right)=2\cdot3+5\cdot2-1\cdot15=1$$

  2. Даны векторы $a=\left(7,11,x\right)$, $b=\left(10,-5,3\right)$, $a\perp b$. Найти $x$.
    Решение

    Воспользуемся следствием для перпендикулярных векторов:$$a\perp b \Leftrightarrow \left(a,b\right)=0$$ $$7\cdot10-11\cdot5+3x=0$$ $$3x=-15$$ $$x=-5$$

  3. Даны векторы $a$ и $b$, $\displaystyle\left|a\right|=15, \left|b\right|=\frac{1}{3}, \angle\left(a,b\right)=\frac{2\pi}{3} $. Найти их скалярное произведение.
    Решение

    Воспользуемся стандартным определением:$$\left(a,b\right)=\left|a\right|\left|b\right|\cos\angle\left(a,b\right)=$$ $$=15\cdot\frac{1}{3}\cdot\cos\left(\frac{2\pi}{3}\right)=$$ $$=15\cdot\frac{1}{3}\cdot\left(-\frac{1}{2}\right)=-2.5$$

  4. Найти угол между векторами $a$ и $b$, если они заданы своими координатами: $a=\left(6,3,0\right)$, $b=\left(-2,-1,\sqrt{5}\right)$.
    Решение

    Воспользуемся следствием для нахождения косинуса:$$\cos\angle\left(a,b\right)=\frac{-6\cdot2-3\cdot1+0\cdot\sqrt{5}}{\sqrt{6^2+3^2+0^2}\sqrt{\left(-2\right)^2}\left(-1\right)^2+\left(\sqrt{5}\right)^2} = \frac{-15}{15\sqrt{2}}=-\frac{1}{2},$$ $$\cos\angle\left(a,b\right)=-\frac{1}{2}\Rightarrow \angle\left(a,b\right)=\frac{3\pi}{4}$$

  5. Найти скалярное произведение векторов $p$ и $q$, если $p=2a-b$, $q=3b+4a$, где $\left|a\right|=4$, $\left|b\right|=3$, $\displaystyle\angle\left(a,b\right)=\frac{\pi}{3}$.
    Решение

    Воспользуемся стандартным определением и алгебраическими свойствами: $$\left(a,b\right)=\left|a\right|\left|b\right|\cos\angle\left(a,b\right)=3\cdot4\cdot\frac{1}{2}=6,$$ $$\left(a,a\right)=\left|a\right|^2=16, \left(b,b\right)=\left|b\right|^2=9,$$ $$\left(p,q\right)=\left(2a-b,3b+4a\right)=3\left(2a-b,b\right)+4\left(2a-b,a\right)=$$ $$=6\left(a,b\right)-3\left(b,b\right)+8\left(a,a\right)-4\left(b,a\right)=2\cdot6+8\cdot16-3\cdot9=113$$

  6. Дан вектор $a=\left(6,-11,2\sqrt{3}\right)$ и вектор $b=\left(\sqrt{3},13,-3\right)$. Найдите $\left\{pr_{a}b\right\}$.
    Решение

    Воспользуемся определением через проекции и определением через координаты: $$\left( a,b \right) = \left|a\right|\left\{pr_{a}b\right\}$$ $$\left\{pr_{a}b\right\}=\frac{\left( a,b \right)}{\left|a\right|}=\frac{6\cdot\sqrt{3}-11\cdot13-3\cdot2\cdot\sqrt{3}}{\sqrt{\left(6\right)^2+\left(-11\right)^2+\left(2\sqrt{3}\right)^2}}=$$ $$=\frac{-11\cdot13}{13}=-11$$

Скалярное произведение векторов

Тест на знание темы «Скалярное произведение векторов, свойства, координатное представление»

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

  1. Воеводин В.В. Линейная алгебра М.: Наука, 1980 (стр. 85-88)
  2. Ильин В.А., Позняк Э.Г. Аналитическая геометрия: Учеб. Для вузов. — 7-е изд., стер. — М.: ФИЗМАТЛИТ, 2004. — 224с. — (Курс высшей математики и математической физики.) (стр. 59-63)
  3. Ефимов Н.В. Краткий курс аналитической геометрии: Учебн. пособие. — 13-еизд., стереот. — М.: ФИЗМАТЛИТ, 2005. — 240с. (стр. 148-153)
  4. Личный конспект, составленный на основе лекций Белозерова Г.С.

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

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

Необходимость. Пусть $A \in M_{n}\left (P\right ).$ И пусть для нее существует правая обратная матрица, тогда, применяя одно из свойств умножения матриц, получаем $AB = E,$ где $E$ — единичная матрица.$$\det(AB)= \det A \det B = 1\Rightarrow \det A\neq 0$$ — по определению матрица $A$ невырожденная.

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

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

Достаточность. Пусть $A \in M_{n}^{0}\left (P\right )$, то есть$\left ( \det A \right )\neq 0$. Укажем обратную матрицу явно. Для удобства обозначим за $$\widetilde{A} = \begin{pmatrix}A_{11} & A_{12} & \cdots & A_{1n}\\ A_{21} & A_{22} & \cdots & A_{2n}\\ \cdots & \cdots & \cdots & \cdots \\ A_{n1} & A_{n2} & \cdots & A_{nn}\end{pmatrix}$$- присоединенную матрицу такую, что $\widetilde{A}=\begin{Vmatrix}A_{ij}\end{Vmatrix}$, где $A_{ij}$ — это алгебраические дополнения к элементу $a_{ij}$ матрицы $A$, $i=\overline{1, n}$ и $j=\overline{1, n}$. Тогда $\left ( \widetilde{A} \right )^{T}=\begin{Vmatrix}A_{ji}\end{Vmatrix}.$

Покажем, что $\displaystyle A^{-1}=\frac{1}{\det A}\left ( \widetilde{A} \right )^{T}.$ Для этого следует проверить выполнение таких равенств: $\displaystyle A\frac{1}{\det A}\left ( \widetilde{A} \right )^{T}=E$ и $\displaystyle \frac{1}{\det A}\left ( \widetilde{A} \right )^{T}A=E.$

Проверим первое равенство. Положим $\displaystyle B=A\cdot \frac{1}{\det A}\left ( \widetilde{A} \right )^{T}$, тогда $$b_{ij}=\sum_{k=1}^{n}a_{ik}\frac{1}{\det A}A_{jk}=\frac{1}{\det A}\sum_{k=1}^{n}a_{ik}A_{jk}.$$

Если $i=j$, то по определению детерминанта получаем $$\displaystyle b_{ij}=\frac{1}{\det A}\det A=1.$$

Если $i\neq j$, то по теореме о «чужих» дополнениях $b_{ij}=0.$

Таким образом, мы доказали, что $\displaystyle E=A\frac{1}{\det A}\left ( \widetilde{A} \right )^{T}.$

Проверим второе равенство. Положим, $\displaystyle C= \frac{1}{\det A}\left ( \widetilde{A} \right )^{T}A.$ Тогда $\displaystyle c_{ij}=\sum_{k=1}^{n}\frac{1}{\det A}A_{jk}a_{ik}=\frac{1}{\det A}\sum_{k=1}^{n}A_{jk}a_{ik}.$ Получаем, что при $i=j$ $\displaystyle c_{ij}=\frac{1}{\det A}\det A=1$, а при $i\neq j\Rightarrow c_{ij}=0.$

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

Следствие. $\det A^{-1}= \left ( \det A \right )^{-1}.$

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

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

  1. Докажите, что матрица $A$ не имеет обратной. $$A=\left (\begin{array}{rrr}1 & 0 & 2 & 1\\ 2 & 3 & 4 & 6\\ 2 & 1 & 2 & 3\\ 0& 1 & -2 & 1\end{array}\right ).$$
    Решение

    Следуя из условия требуется показать, что исходная матрица не удовлетворяет условиям критерия обратимости квадратных матриц. Проверим матрицу на невырожденность, для этого сначала приведем данную матрицу к треугольному виду методом Гаусса. Получаем $$A=\left (\begin{array}{rrr}1 & 0 & 2 & 1\\ 2 & 3 & 4 & 6\\ 2 & 1 & 2 & 3\\ 0 & 1 & -2 & 1\end{array}\right )\sim\left (\begin{array}{rrr}2 & 3 & 4 & 6\\ 2 & 1 & 2 & 3\\ 1 & 0& 2 & 1\\ 0 & 1 & -2 & 1\end{array}\right )\sim\left (\begin{array}{rrr}2 & 3 & 4 & 6\\ 2 & 1 & 2 & 3\\ 0 & -\frac{1}{2} & 1 & -\frac{1}{2}\\ 0 & 1 & -2 & 1\end{array}\right )\sim$$$$\left (\begin{array}{rrr}2 & 3 & 4 & 6\\ 0 & -2 & -2 & -3\\ 0 & 1 & -2 & 1\\ 0 & -\frac{1}{2} & 1 & -\frac{1}{2}\end{array}\right )\sim \left (\begin{array}{rrr}2 & 3 & 4 & 6\\ 0 & -2 & -2 & -3\\ 0 & 1 & -2 & 1\\ 0 & 0 & 0 & 0\end{array}\right ).$$ Видим, что матрица имеет нулевую строку, по третьему свойству определителей, определитель данной матрицы равен нулю, а это по определению означает, что исходная матрица вырождена. Следовательно, исходная матрица не имеет обратной.

  2. Найти значение выражения $\left ( \det A \right )^{-1}+3\det B^{-1}$, не вычисляя обратные матрицы, где $$A=\left (\begin{array}{rrr}0 & 1 & 2 \\ 0 & 3 & 7 \\ 1 & 2 & 3\end{array}\right ),\, B=\left (\begin{array}{rrr}1 & 0 & 2 \\ 4 & 3 & 1 \\ 2 & 0 & 3\end{array}\right ).$$

    Решение

    По следствию из критерия обратимости квадратных матриц получаем $\det A^{-1}+3\det B^{-1}.$ Так из лекции обратимость матриц мы знаем, что $\displaystyle \det A^{-1}= \frac{1}{\det A}.$$$\det A= \left| \begin{array}{rrr}0 & 1 & 2 \\ 0 & 3 & 7\\ 1 & 2 & 3\end{array}\right |=7-6=1,\, \det B=\left |\begin{array}{rrr}1 & 0 & 2\\ 4 & 3 & 1\\ 2 & 0 & 3\end{array}\right |=9-12=-3.$$ Тогда $\displaystyle \frac{1}{1}+3\left (-\frac{1}{3}\right )=1-1=0.$

    Ответ: $0.$

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

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

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

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

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

Пусть дана система линейных уравнений (СЛАУ) $$\left.\begin{matrix} a_{11}x_{1} & + & \cdots & + & a_{1n}x_{n} & = & b_{1} \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ a_{m1}x_{2} & + & \cdots & + & a_{mn}x_{n} & = & b_{m} \end{matrix}\right\},$$ где $a_{11}, a_{1n}, a_{m1}, a_{mn}$ — числовые коэффициенты, $x_{1},x_{2},x_{3}$ — переменные, $b_{1},b_{m}$ — свободные члены.

Обозначим матрицу-столбец неизвестных $(X)$, матрицу коэффициентов при неизвестных $(A)$ и столбец правых частей $(B)$: $$X = \begin{Vmatrix} x_{1}\\ \vdots \\ x_{n}\\ \end{Vmatrix}, \quad A = \begin{Vmatrix} a_{11} & \cdots & a_{1n}\\ \cdot & \cdot & \cdot \\ a_{m1} & \cdots & a_{mn} \end{Vmatrix},\quad B=\begin{Vmatrix}b_{1}\\ \vdots \\ b_{m}\end{Vmatrix}.$$

Соотношения, задаваемые системой, запишем в виде матричного уравнения $(A \cdot X = B)$: $$\begin{Vmatrix}x_{1}\\ \vdots \\ x_{n}\\ \end{Vmatrix}\cdot \begin{Vmatrix} a_{11} & \cdots & a_{1n}\\ \cdot & \cdot & \cdot \\ a_{m1} & \cdots & a_{mn} \end{Vmatrix} = \begin{Vmatrix}b_{1}\\ \vdots \\ b_{m}\end{Vmatrix}.$$

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

Теорема. Пусть задана СЛАУ от $n$ неизвестных с квадратной невырожденной матрицей над полем $P$. Тогда общее решение такой системы содержит лишь одно частное решение $(x_{1}^{0}, \; x_{2}^{0}, \; \cdots , \; x_{n}^{0}) \in P^{n}$, которое находится по формуле $x_{i}^{0} = \frac{\Delta_{i}}{\Delta}, \; i = 1, \; \ldots \;,n$, где $\Delta$ — определитель матрицы системы, а $\Delta_{i}$ — определитель, получаемый из этой матрицы заменой $i$-го столбца столбцом свободных членов системы.

Докажем теорему, воспользовавшись матричным уравнением $A \cdot X = B:$ $$\begin{Vmatrix}x_{1}\\ \vdots \\ x_{n}\\ \end{Vmatrix}\cdot \begin{Vmatrix} a_{11} & \cdots & a_{1n}\\ \cdot & \cdot & \cdot \\ a_{m1} & \cdots & a_{mn} \end{Vmatrix} = \begin{Vmatrix}b_{1}\\ \vdots \\ b_{m}\end{Vmatrix}.$$

Единственность. Пусть имеется решение уравнения $X_{0}$. Тогда $A \cdot X_{0} = B$. Так как определитель матрицы отличен от нуля можем быть уверены, что существует обратная к $A$ матрица $A^{-1}$. Умножим обе части равенства слева на $A^{-1}$: $$ A^{-1} \cdot\left(A \cdot X_{0}\right)=\left(A^{-1} \cdot A\right) \cdot X_{0}=E \cdot X_{0}=X_{0}=A^{-1} \cdot B.$$ Следовательно, если решение существует, то оно неизбежно будет равно $A^{-1} \cdot B$.

Существование. Сделаем замену: $X_{0} = A^{-1} \cdot B$. Подставим в уравнение: $$ A \cdot\left(A^{-1} \cdot B\right)=\left(A \cdot A^{-1}\right) \cdot B=E \cdot B=B.$$ Делаем вывод что, решение существует. Используя явное представление обратной матрицы, можем показать явный вид решения: $$A^{-1} \cdot B=\Delta^{-1} \cdot\begin{Vmatrix} A_{11} & \ldots & A_{n1}\\ \cdot & \cdot & \cdot \\ A_{1n} & \ldots & A_{nn} \end{Vmatrix} \cdot \begin{Vmatrix}b_{1} \\ \vdots \\ b_{n} \end{Vmatrix} = \Delta^{-1} \cdot \begin{Vmatrix} \sum\limits_{j = 1}^{n} A_{j1} \cdot b_{j}\\ \vdots\\ \sum\limits_{j = 1}^{n} A_{jn} \cdot b_{j} \end{Vmatrix}.$$

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

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

  1. Находим определитель матрицы искомой системы $\Delta = \begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \cdot & \cdot & \cdot \\ a_{m1} & \cdots & a_{mn} \end{vmatrix}$. Определитель обязательно должен быть отличен от нуля.
  2. Находим определители матриц $\Delta_{x_{n}} = \begin{vmatrix} a_{11} & a_{12} & \cdots & b_{1} \\ a_{21} & a_{22} & \cdots & b_{2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & b_{n} \end{vmatrix}$, в которых $k$-ые столбцы $(k = 1,2, \; \ldots, n)$ заменены на столбец свободных членов системы.
  3. Вычисляем неизвестные переменные по формуле: $x_{n} = \frac{\Delta_{x_{n}}}{\Delta }$.
  4. Выполняем проверку решения, подставив $x_{k} (k = 1,2, \ldots, n)$ в исходную систему. Все уравнения системы должны быть тождественно равны.

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

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

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

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

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

  1. Решить систему уравнений методом Крамера $$ \left\{\begin{array}{l} 2 x_{1}- x_{2}- x_{3}=4 \\ 3 x_{1}+4x_{2}-2 x_{3}=11 \\ 3 x_{1}-2 x_{2}+4x_{3}=11 \end{array}\right.$$
    Решение

    Вычислим определитель матрицы системы с помощью правила треугольника: $$ \Delta = \left|\begin{array}{} 2& -1& -1 \\ 3& 4& -2 \\ 3& -2& 4 \end{array}\right| = 60,$$ $\Delta = 60 \neq 0$, значит эта система имеет решение, причем единственное.

    Найдем с помощью правила треугольника определители $\Delta_{i}$ ($i$-ый столбец заменяется на столбец свободных членов), где $i = 1,2,3:$ $$\Delta_{1} = \begin{vmatrix} 4 & -1& -1\\ 11& 4& -2\\ 11& -2& 4 \end{vmatrix} = 180,$$ $$\Delta_{2} = \begin{vmatrix} 2& 4& -1\\ 3& 11& -2\\ 3& 11& 4 \end{vmatrix} = 60,$$$$\Delta_{3} = \begin{vmatrix} 2& -1& 4\\ 3& 4& 11\\ 3& -2& 11 \end{vmatrix} = 60.$$

    Находим неизвестные $x_{n} = \frac{\Delta _{n}}{\Delta}:$ $$x_{1} =\frac{\Delta_{1}}{\Delta} = \frac{180}{60} = 3;$$ $$x_{2} =\frac{\Delta_{2}}{\Delta} = \frac{60}{60} = 1;$$ $$x_{3} =\frac{\Delta_{3}}{\Delta} = \frac{60}{60} = 1;$$ Ответ:$\; x_{1} = 3; \; x_{2} = 1; \; x_{3} = 1$.

    [свернуть]
  2. Решить систему уравнений методом Крамера $$ \left\{\begin{matrix} ax — 3y = 1 \\ 2x +ay = 2 \end{matrix}\right.$$
    Решение

    Здесь $a$ — некое вещественное число. Найдем определитель системы: $$\Delta =\begin{vmatrix} a & -3\\ 2& a \end{vmatrix} = a^{2} + 6.$$

    Находим дополнительные определители $\Delta_{i}$($i$-ый столбец заменяется на столбец свободных членов):$$ \Delta_{x} = \begin{vmatrix} 1 & -3\\ 2 & a \end{vmatrix} = a+6,$$ $$\Delta_{y} = \begin{vmatrix} a & 1\\ 2 & 2 \end{vmatrix} = 2a-2 = 2(a — 2).$$ Находим неизвестные: $$x = \frac{a + 6}{a^{2} + 6},$$ $$y = \frac{2(a — 1)}{a^{2} + 6}.$$

    [свернуть]
  3. Решить систему уравнений методом Крамера $$ \left\{\begin{array}{} x_{1}+ x_{2}+2 x_{3}=-1 \\ 2 x_{1}- x_{2}+2 x_{3}=-4 \\ 4 x_{1}+x_{2}+4_{3}=-2 \end{array}\right. $$
    Решение

    Вычислим определитель матрицы с помощью правила треугольника: $$\Delta = \begin{vmatrix} 1& 1& 2\\ 2& -1& 2\\ 4& 1& 4 \end{vmatrix} = 6,$$ $\Delta = 6 \neq 0$, значит эта система имеет решение, причем единственное.

    Найдем с помощью правила треугольника определители $\Delta_{i}$ ($i$-ый столбец заменяется на столбец свободных членов), где $i = 1,2,3:$ $$\Delta_{1} = \begin{vmatrix} -1& 1& 2\\ -4& -1& 2\\ -2& 1& 4 \end{vmatrix} = 6,$$ $$ \Delta_{2} = \begin{vmatrix} 1& -1& 2\\ 2& -4& 2\\ 4& -2& 4 \end{vmatrix} = 12,$$ $$ \Delta_{3} = \begin{vmatrix} 1& 1& -1\\ 2& -1& -4\\ 4& 1& -2 \end{vmatrix} = -12.$$

    Находим неизвестные $x_{n} = \frac{\Delta _{n}}{\Delta}:$ $$x_{1} =\frac{\Delta_{1}}{\Delta} = \frac{6}{6} = 1;$$ $$x_{2} =\frac{\Delta_{1}}{\Delta} = \frac{12}{6} = 2;$$ $$x_{3} =\frac{\Delta_{1}}{\Delta} = \frac{-12}{6} = -2;$$ Ответ:$\; x_{1} = 1; \; x_{2} = 2; \; x_{3} = -2$.

    [свернуть]
  4. Найти количество решений у системы уравнений $$ \left\{\begin{array}{} 2 x_{1}+ 3x_{2}- x_{3}=3 \\ 4 x_{1}+6x_{2}-2x_{3}=6 \\ 3 x_{1}-x_{2}+2x_{3}=-1 \end{array}\right.$$
    Решение

    Вычислим определитель матрицы с помощью правила треугольника: $$\Delta = \begin{vmatrix} 2& 3& -1\\ 4& 6& -2\\ 3& -1& 2 \end{vmatrix} = 0,$$ $\Delta = 0$, значит эта система имеет либо бесконечное количество решений, либо вообще не имеет.

    Найдем с помощью правила треугольника определители $\Delta_{i}$ ($i$-ый столбец заменяется на столбец свободных членов), где $i = 1,2,3:$ $$ \Delta_{1} = \begin{vmatrix} 3& 3& -1\\ 6& 6& -2\\ -1& -1& 2 \end{vmatrix} = 0,$$ $$ \Delta_{2} = \begin{vmatrix} 2& 3& -1\\ 4& 6& -2\\ 3& -1& 2 \end{vmatrix} = 0,$$ $$ \Delta_{3} = \begin{vmatrix} 2& 3& 3\\ 4& 6& 6\\ 3& -1& -1 \end{vmatrix} = 0.$$

    По следствию 1 выясняем, что система уравнений имеет бесконечное количество решений.

    [свернуть]
  5. Решить систему уравнений методом Крамера $$ \left\{\begin{array}{}2x_{1}+6x_{2}+4x_{3}=8 \\x_{1}+5x_{2}+4x_{3}=8 \\x_{1}+5x_{2}+7x_{3}=17\end{array}\right.$$
    Решение

    Вычислим определитель матрицы с помощью правила треугольника: $$\Delta = \begin{vmatrix} 2& 6& 4\\ 1& 5& 4\\ 1& 5& 7 \end{vmatrix} = 12,$$ $\Delta = 12 \neq 0$, значит эта система имеет решение, причем единственное.

    Найдем с помощью правила треугольника определители $\Delta_{i}$ ($i$-ый столбец заменяется на столбец свободных членов), где $i = 1,2,3:$ $$ \Delta_{1} = \begin{vmatrix} 8& 6& 4\\ 8& 5& 4\\ 17& 5& 7 \end{vmatrix} = 12,$$ $$ \Delta_{2} = \begin{vmatrix}2& 8& 4\\ 1& 8& 4\\ 1& 17& 7 \end{vmatrix} = -12,$$ $$ \Delta_{3} = \begin{vmatrix} 2& 6& 8\\ 1& 5& 8\\ 1& 5& 17 \end{vmatrix} = 36.$$

    Находим неизвестные $x_{n} = \frac{\Delta _{n}}{\Delta}:$ $$x_{1} =\frac{\Delta_{1}}{\Delta} = \frac{12}{12} = 1;$$ $$x_{2} =\frac{\Delta_{1}}{\Delta} = \frac{-12}{12} = -1;$$ $$x_{3} =\frac{\Delta_{1}}{\Delta} = \frac{36}{12} = 3;$$ Ответ:$\; x_{1} = 1; \; x_{2} = -1; \; x_{3} = 3$.

    [свернуть]

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

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

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

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

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

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

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

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

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

Пусть нам нужно найти корни многочлена $P\left(x\right),$ то есть решить уравнение $P\left(x\right)=0.$ $P\left(x\right)$ представим в виде: $$\displaystyle\sum\limits_{i=0}^n{a_{i}x^i} = a_{n}x^n + a_{n-1}x^{n-1} + \ldots +\ a_{1}x + a_{0}. $$ Решение может осуществляться методами, которые используют производные (если нам нужно найти только действительные корни), а также любыми итерационными способами. Последний требует многократного вычисления значений многочлена.

По следствию из теоремы Безу, многочлен $P\left(x\right)$ можно представить в виде: $$P\left(x\right) = \left(x-x_{0}\right)Q\left(x\right) + R\left(x\right),$$ где $Q\left(x\right)\ — $ результат деления $P\left(x\right)$ на $\left(x-x_{0}\right),\ R\left(x\right)\ — $ остаток от этого деления. Обозначим $Q\left(x\right)$ как $b_{n-1}x^{n-1} + b_{n-2}x^{n-2} + \ldots + b_{0}.$ Перепишем наш многочлен: \begin{multline}\underbrace{a_{n}x^n + a_{n-1}x^{n-1} + \ldots + a_{1}x + a_{0}}_{P\left(x\right)} \equiv \\ \equiv \left(x-x_{0}\right)\underbrace{\left(b_{n-1}x^{n-1} + b_{n-2}x^{n-2} + \ldots + b_{0}\right)}_{Q\left(x\right)} + R\left(x\right). \end{multline} Для того чтобы вычислить значения многочлена, нам необходимо при заданном $x = x_{0}$ найти степени $x_{0}^k,\ \left(k = \overline{1,n}\right),$ результаты умножить на коэффициенты $\left(b_{n-1}, b_{n-2}, \ldots, b_{0}\right)$, а получившееся сложить. Однако, чтобы ускорить процесс и вдвое сократить количество умножений, можно воспользоваться алгоритмом Горнера. Выведем его.

Алгоритм берет свое начало из теоремы Безу, которая звучит так: если многочлен $P\left(x\right)$ разделить на двучлен $\left(x-x_{0}\right),$ то остаток от этого деления будет равен значению $P\left(x\right)$ на элементе $x_{0},$ т.е. (остаток)$R\left(x\right) = P\left(x_{0}\right).$

В тождестве $\left(1\right)$ умножим $\left(x-x_{0}\right)$ на $Q\left(x\right)$. Получаем $$a_{n}x^n + a_{n-1}x^{n-1} + \ldots + a_{1}x + a_{0} \equiv \\ \equiv b_{n-1}x^n + b_{n-2}x^{n-1} + \ldots + b_{0}x-\\-x_{0}b_{n-1}x^{n-1}-x_{0}b_{n-2}x^{n-2}-\ldots-x_{0}b_{0} + R\left(x\right).$$ Теперь приравняем коэффициенты при одинаковых степенях $x:$ $b_{n-1} = a_{n};\ b_{n-2} = a_{n-1}+x_{0}b_{n-1};\ \ldots;\ R\left(x\right) = a_{0}+x_{0}b_{0}.$ Приходим к исходному: $R\left(x\right)=P\left(x_{0}\right).$ Результаты оформим в виде таблицы:

$a_n$ $a_{n-1}$ $\ldots$ $a_0$
$x_0$ $b_{n-1}$ $b_{n-2}$ $\ldots$ $R\left(x\right)$

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

Замечание: помимо значения остатка $R\left(x\right),$ алгоритм дает нам $Q\left(x\right)$ (неполное частное). Также, если остаток $R\left(x\right)=0,$ то $x_{0} — $ корень многочлена $P\left(x\right).$

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

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

  1. Разделить многочлен $P_{5}\left(x\right) = x^5-8x^4+7x^3-4x^2+16x+24$ на $\left(x-2\right).$
    Решение

    Вместо деления уголком, воспользуемся алгоритмом Горнера:

    $1$ $-8$ $7$ $-4$ $16$ $24$
    $2$ $1$

    В ячейки, выделенные розовым, записываем коэффициенты многочлена $P_5\left(x\right),$ а в желтую ячейку — $x_0.$ Оставшееся место в таблице будем заполнять вычислениями. Первое число всегда сносим без изменений.

    $1$ $-8$ $7$ $-4$ $16$ $24$
    $2$ $1$ $-6$

    $x_0$ умножаем на число в ячейке напротив, складываем со следующим коэффициентом $P_5\left(x\right),$ и под ним записываем результат (в зеленой ячейке). Дальше продолжаем выполнять действия, которые указаны выше. Получаем таблицу:

    $1$ $-8$ $7$ $-4$ $16$ $24$
    $2$ $1$ $-6$ $-5$ $-14$ $-12$ $0$

    Область, выделенная голубым — это получившиеся коэффициенты нового многочлена $Q\left(x\right),$ а фиолетовым — остаток $R\left(x\right).$

    Ответ: $P_5\left(x\right) = x^5-8x^4+7x^3-4x^2+16x+24= \\ =\left(x-2\right)\left(x^4-6x^3-5x^2-14x^2-12x\right) + 0.$

    Заметим, что степень $Q\left(x\right)$ всегда на $1$ меньше степени $P\left(x\right).$ Также, выше было сказано, что если $R\left(x\right)=0,$ то $x_{0} — $ корень многочлена. В данном случае $x_{0}$ является корнем $P_{5}\left(x\right).$

    [свернуть]
  2. Определить кратность корня $x_{0}=1$ многочлена $P_{5}\left(x\right)=x^5-8x^3+14x^2-9x+2.$
    Решение

    Кратность корня определяется количеством нулевых остатков от деления $P\left(x\right)$ на $\left(x-x_{0}\right).$ Воспользуемся схемой Горнера:

    $1$ $0$ $-8$ $14$ $-9$ $2$
    $1$ $1$ $1$ $-7$ $7$ $-2$ $0$

    Так как $R\left(x\right)=0,$ мы можем проверить, является ли $x_0=1$ корнем для уже нового многочлена $Q\left(x\right).$ Продолжаем заполнять таблицу по тому же принципу.

    $1$ $0$ $-8$ $14$ $-9$ $2$
    $1$ $1$ $1$ $-7$ $7$ $-2$ $0$
    $1$ $1$ $2$ $-5$ $2$ $0$
    $1$ $1$ $3$ $-2$ $0$
    $1$ $1$ $4$ $2$

    В последней строке мы получили ненулевой остаток. Значит, вычисления можно закончить. Определяем кратность по количеству нулей на «лесенке». Записываем получившееся разложение: $$P_5\left(x\right) = x^5-8x^3+14x^2-9x+2 = \left(x-1\right)^3\left(x^2+3x-2\right).$$

    Ответ: $x_0$ для многочлена $P_5\left(x\right)$ является корнем третьей кратности.

    [свернуть]
  3. При каких значениях $A$ и $B$ многочлен $P_4\left(x\right) = Ax^4 + Bx^2 + 1$ делится на $\left(x-1\right)^2?$
    Решение

    Перефразируем условие задачи для лучшего понимания: при каких $A$ и $B$ число $x_0$ будет корнем $P_4\left(x\right)$, кратности не ниже $2?$ Воспользуемся алгоритмом Горнера.

    $A$ $0$ $B$ $0$ $1$
    $1$ $A$ $A$ $A+B$ $A+B$ $A+B+1$
    $1$ $A$ $2A$ $3A+B$ $4A+2B$
    $1$ $A$ $3A$ $6A+B$

    Можем сделать вывод, что кратность корня будет не ниже двух тогда и только тогда, когда $\begin{cases}A + B + 1 = 0 \\ 4A + 2B = 0\end{cases}.$ Отсюда $A = 1, B= -2.$ Однако, есть вероятность, что при этих же значениях $A$ и $B$ кратность корня будет больше. Для этого мы и записали последнюю строку в таблице. Не составляет труда проверить, что $6A + B = 6 \cdot 1 + \left(-2\right) = 4 \neq 0 \Rightarrow$ кратность корня равна двум, ни больше, ни меньше.

    Ответ: $\left(x-1\right)^2$ делит $P_4\left(x\right) \Leftrightarrow A=1,\ B=-2.$ $\left(x-1\right)^3$ не делит $P_4\left(x\right)$ ни при полученных значениях $A$ и $B,$ ни при каких других.

    [свернуть]
  4. Дан многочлен $P_4\left(x\right) = x^4-\left(2+i\right)x^3-\left(3+2i\right)x + 5$ над полем $\usepackage{amsfonts}\mathbb{C}$. Разделить его с остатком на $\left(x-x_0\right),$ где $x_0 = 1-i,$ попутно вычислив $P_4\left(x_0\right).$
    Решение

    Используем схему Горнера таким же образом, как в примерах выше.

    $1$ $-2-i$ $0$ $-3-2i$ $5$
    $1-i$ $1$ $-1-2i$ $-3-i$ $-7$ $2-7i$
    1. $1-i-2+i = \mathbf{-1-2i};$
    2. $\left(-1-2i\right)\left(1-i\right) = -1+i-2i+2i^2 = -1-i-2 = \mathbf{-3-i};$
    3. $\left(-3-i\right)\left(1-i\right) = -3+3i-i+i^2 = -3+2i-1 = -4+2i; \\ -4+2i-3-2i = \mathbf{-7};$
    4. $\left(-7\right)\left(1-i\right) = -7-7i; \\ -7-7i+5 = \mathbf{2-7i}.$

    Ответ: $P_4\left(x\right) = \left(x-\left(1-i\right)\right)\left(x^3+\left(-1-2i\right)x^2+\left(-3-i\right)x-7\right)+\left(2-7i\right);$ $P_4\left(x_0\right) = 2-7i.$

    [свернуть]

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

После ознакомления с примерами решения задач, можно приступить к изучению данного вопроса. Представим многочлен уже привычным нам образом $P\left(x\right) = a_{n}x^n + a_{n-1}x^{n-1} + \ldots + a_{1}x + a_{0}.$ Сделаем самое очевидное действие — вынесем $x$ за скобки: $x\left(a_{n}x^{n-1} + a_{n-1}x^{n-2} + \ldots + a_{1}\right) + a_{0}.$ Если мы повторим это действие $n-1$ раз, то получим $$\underbrace{x(x(x\ldots}_{n-1}\left(a_{n}x+a_{n-1}\right)+\ldots \left)+a_1\right)+a_0.$$ Алгоритм Горнера работает вне зависимости от того, какая степень у многочлена — схема универсальна. Посмотрим на примере. \begin{multline}P_7\left(x\right) = x^7+5x^6-2x^5-x^4+3x^2-8x+11 = \\ = x\left(x^6+5x^5-2x^4-x^3+3x-8\right)+11 = \\ = x\left(x\left(x^5+5x^4-2x^3-x^2+3\right)-8\right)+11 = \\ = x\left(x\left(x\left(x^4+5x^3-2x^2-x+0\right)+3\right)-8\right)+11 = \\ = x\left(x\left(x\left(x\left(x^3+5x^2-2x-1\right)+0\right)+3\right)-8\right)+11 = \\ = x\left(x\left(x\left(x\left(x\left(x^2+5x-2\right)-1\right)+0\right)+3\right)-8\right)+11 = \\ = \underbrace{x(x(x(x(x(x}_{(n-1)=(7-1)=6} (x+5)-2)-1)+0)+3)-8)+11 = \\ = x\left(x\left(x\left(x\left(x\left(x\left(\left(1\cdot x\right)+5\right)-2\right)-1\right)+0\right)+3\right)-8\right)+11. \end{multline} Отсюда видим, для того чтобы посчитать выражение $\left(2\right),$ мы должны $1$ (коэффициент перед $x^7$) умножить на $x,$ результат прибавить к $5$ (коэффициент перед $x^6$), опять умножить на $x$ и т.д. То есть мы делаем все то, что и в схеме Горнера.

Почему разложение $P\left(x\right) = \left(x-x_0\right)Q\left(x\right)+R\left(x\right)$ — верно? Начнем с арифметики. Возьмем какое-то натуральное число $a.$ Как гласит нам основная теорема арифметики, его всегда можно представить в виде произведения двух других чисел с остатком, то есть $a = s \cdot q + r.$ Например, $7 = 2 \cdot 3 +1,$ $8 = 4 \cdot 2 + 0.$ Разложение такого типа единственно, причем $0 \leqslant r < s.$

Тоже самое происходит и с многочленами. Допустим, мы хотим разделить многочлен $P\left(x\right)$ на $Q\left(x\right)$ с остатком. Значит $P\left(x\right)$ можно записать как $P\left(x\right) = S\left(x\right) \cdot Q\left(x\right) + R\left(x\right),$ где $0 \leqslant \deg{R}\left(x\right) < \deg{Q}\left(x\right).$

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

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

  1. Разложить многочлен $P_6(x) = x^6+6x^5+3x^4-28x^3-9x^2+54x-27$ по степеням $\left(x-1\right).$
    Решение

    Ответ будет выглядеть как формула Тейлора: $P\left(x\right) = h_n\left(x-x_0\right)^n+ h_{n-1}\left(x-x_0\right)^{n-1} + h_{n-2}\left(x-x_0\right)^{n-2} + \ldots + \\ + h_{2}\left(x-x_0\right)^2 + h_{1}\left(x-x_0\right) + h_0.$

    Общий вид схемы Горнера для решения задачи:

    $a_n$ $a_{n-1}$ $a_{n-2}$ $\ldots$ $a_2$ $a_1$ $a_0$
    $x_0$ $b_{n-1}$ $b_{n-2}$ $b_{n-3}$ $\ldots$ $b_1$ $b_0$ $h_0$
    $x_0$ $с_{n-1}$ $с_{n-2}$ $с_{n-3}$ $\ldots$ $с_1$ $h_1$
    $x_0$ $d_{n-1}$ $d_{n-2}$ $d_{n-3}$ $\ldots$ $h_2$
    $\ldots$ $\ldots$ $\ldots$ $\ldots$ $\mathinner{\mkern2mu\raise1pt\hbox{.}\mkern2mu \raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}$
    $x_0$ $f_{n-1}$ $f_{n-2}$ $h_{n-2}$
    $x_0$ $g_{n-1}$ $h_{n-1}$
    $x_0$ $h_n$

    $a_n = b_{n-1} = c_{n-1} = d_{n-1} = \ldots = f_{n-1} = g_{n-1} = h_n.$

    $1$ $6$ $3$ $-28$ $-9$ $54$ $-27$
    $1$ $1$ $7$ $10$ $-18$ $-27$ $27$ $0$
    $1$ $1$ $8$ $18$ $0$ $-27$ $0$
    $1$ $1$ $9$ $27$ $27$ $0$
    $1$ $1$ $10$ $37$ $64$
    $1$ $1$ $11$ $48$
    $1$ $1$ $12$
    $1$ $1$

    Ответ: $P_6\left(x\right)=64\left(x-1\right)^3+48\left(x-1\right)^4+12\left(x-1\right)^5+\left(x-1\right)^6.$

    [свернуть]
  2. Найти все рациональные корни многочлена $P_7\left(x\right) = 9x^7+3x^6-23x^5+4x^4-5x^3+23x^2-13x+2.$
    Решение

    В таких заданиях всегда в первую очередь проверяются корни $\pm 1$ и их кратность. Получается разложение $P\left(x\right) = \left(x-1\right)^{k}\left(x+1\right)^{l}g\left(x\right),$ где $k\ — $ кратность корня $1,$ $l\ $ кратность корня $-1,$ $g\left(x\right) = b_{m}x^m + b_{m-1}x^{m-1} + \ldots + b_{1}x + b_0$ $\left(m = n-k-l\right).$ Числа $\pm 1$ не являются корнями $g\left(x\right)$.

    Введём $x_0=\displaystyle\frac{s}{t},$ где $s \in \mathcal{S},\ t \in \mathcal{T},\ x_0 \in \mathcal{X},\ \mathcal{S}\ — $ множество всех делителей $a_0,$ $\mathcal{T}\ — $ множество всех положительных делителей $a_n,$ $\mathcal{X}\ — $ множество всех дробей, которые потенциально являются корнями.

    Отбор потенциальных корней (кроме $\pm 1$) приводит к множествам: $$\mathcal{S} = \big\{s \in \mathbb{Z} : s|b_0\big\},\ \mathcal{T} = \big\{t \in \mathbb{Z} : \left(t|b_m \right)\wedge\left(t>0 \right)\big\},$$ $$\mathcal{X} = \bigg\{\displaystyle\frac{s}{t} \in \mathbb{Q} : s \in \mathcal{S},\ t \in \mathcal{T}\bigg\}.$$ Их формирование будет происходить уже для $g\left(x\right).$

    Сначала проверим по Горнеру, являются ли $\pm 1$ корнями $P_7\left(x\right).$

    $9$ $3$ $-23$ $4$ $-5$ $23$ $-13$ $2$
    $1$ $9$ $12$ $-11$ $-7$ $-12$ $11$ $-2$ $0$
    $1$ $9$ $21$ $10$ $3$ $-9$ $2$ $0$
    $1$ $9$ $30$ $40$ $43$ $34$ $36$
    $-1$ $9$ $12$ $-2$ $5$ $-14$ $16$

    По таблице видно, что $x_0=1\ — $ корень второй кратности, а $x_0=-1$ корнем не является. Получаем разложение: $$P_7\left(x\right) = \left(x-1\right)^{2}g\left(x\right),$$ $$g\left(x\right) = 9x^5+21x^4+10x^3+3x^2-9x+2.$$Также мы определили значения $g\left(1\right) = 36$ и $g\left(-1\right) = 16.$

    Для свободного члена $b_0 = 2$ формируем $\mathcal{S}\ — $ множество всех его целых делителей, а для $b_m = 9$ формируем $\mathcal{T}\ — $ множество всех его натуральных делителей. \begin{eqnarray*}\mathcal{S} = \{2;\ -2;\ 1;\ -1\},\ \mathcal{T} = \{9;\ 3;\ 1\}. \end{eqnarray*}

    Формируем множество $\mathcal{X},$ которое состоит из всех вариаций $x_0 = \displaystyle\frac{s}{t},$ где $s \in \mathcal{S},$ а $t \in \mathcal{T}.$ Все полученные числа записываем дробями: $$\mathcal{X} = \bigg\{\displaystyle\frac29;\ \displaystyle\frac23;\ \displaystyle\frac21;\ \displaystyle\frac{-2}9;\ \displaystyle\frac{-2}3;\ \displaystyle\frac{-2}1;\ \displaystyle\frac19;\ \displaystyle\frac13;\ \displaystyle\frac11;\ \displaystyle\frac{-1}9;\ \displaystyle\frac{-1}3;\ \displaystyle\frac{-1}1\bigg\}.$$

    Сразу вычеркиваем дроби со значениями $\pm 1.$ То что остается, проверяем на двух тестах:

    1. $t-s|g \left(1 \right);$
    2. $t+s|g \left(-1 \right).$

    Все тесты проходят дроби: $$\mathcal{X}^\prime = \bigg\{-2;\ \displaystyle\frac13;\ \displaystyle-\frac{1}3\bigg\}.$$

    Теперь, каждое из этих чисел проверим с помощью алгоритма Горнера.

    $9$ $21$ $10$ $3$ $-9$ $2$
    $-2$ $9$ $3$ $4$ $-5$ $1$ $0$
    $-2$ $9$ $-15$ $34$ $-73$ $-145$
    $\displaystyle\frac13$ $9$ $6$ $6$ $-3$ $0$
    $\displaystyle\frac13$ $9$ $9$ $9$ $0$
    $\displaystyle\frac13$ $9$ $12$ $13$
    $\displaystyle-\frac13$ $9$ $6$ $7$

    Нам подходят строки с нулевым остатком. Запишем получившееся разложение: $g\left(x\right) = \left(x-\displaystyle\frac13\right)^2\left(x+2\right)\left(9x^2+9x+9\right) = \\ = 9\left(x-\displaystyle\frac13\right)^2\left(x+2\right)\left(x^2+x+1\right).$

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

    Ответ: корни $P_7\left(x\right):\ 1;\ -2;\ \displaystyle\frac13.$

    [свернуть]

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

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

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

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