1. Если дана матрица , то ее характеристическое (вековое) уравнение записывается в виде
. (81)
В левой части этого уравнения стоит характеристический многочлен -й степени . Для непосредственного вычисления коэффициентов этого многочлена нужно раскрыть характеристический определитель , а это связано при больших с большим объемом вычислительной работы, поскольку входит в диагональные элементы определителя.
Академик А. Н. Крылов в 1937 г. предложил преобразование характеристического определителя, в результате которого входит только в элементы одного столбца (или строки). Преобразование Крылова существенно упрощает вычисление коэффициентов характеристического уравнения.
В этом параграфе мы дадим алгебраический вывод преобразованного характеристического уравнения, несколько отличающийся от вывода самого Крылова.
Введем в рассмотрение -мерное векторное пространство с базисом и линейный оператор в , определяемый данной матрицей при этом базисе. Выберем в произвольный вектор и составим ряд векторов
Пусть
первые векторов
этого ряда 
линейно
независимы, а -й
вектор есть
линейная комбинация этих векторов:
Все дальнейшие векторы ряда (82) также линейно выражаются через первые векторов этого ряда. Таким образом, в ряду (82) имеется линейно независимых векторов, и это максимальное число линейно независимых векторов ряда (82) может быть всегда реализовано на первых векторах ряда.
Многочлен является минимальным (аннулирующим) многочленом вектора относительно оператора (см. § 1). Метод А. Н. Крылова есть метод эффективного определения минимального многочлена вектора .
Мы рассмотрим раздельно два случая: регулярный случай, когда , и особый случай, когда .
Многочлен является делителем минимального многочлена всего пространства , а в свою очередь является делителем характеристического многочлена . Поэтому всегда является делителем .
В регулярном случае и имеют одну и ту же степень , и поскольку старшие коэффициенты у них равны, то эти многочлены совпадают. Таким образом, в регулярном случае
,
и потому метод Крылова в регулярном случае есть метод вычисления коэффициентов характеристического многочлена .
В особом случае, как мы увидим ниже, метод Крылова не дает возможности определить и в этом случае он определяет только многочлен , являющийся делителем .
При изложении преобразования Крылова мы будем обозначать координаты вектора в заданном базисе через , а координаты вектора через .
2. Регулярный случай: . В этом случае векторы линейно независимы, и равенства (83), (84), (85) принимают вид
Условие лилейной независимости векторов может быть аналитически записано так (см. гл. III, § 1):
. (89)
Рассмотрим матрицу, составленную из координат векторов :
. (90)
В регулярном случае ранг этой матрицы равен . Первые строк этой матрицы линейно независимы, а последняя, -я, строка есть линейная комбинация предыдущих .
Зависимость между строками матрицы (90) получим, заменяя векторное равенство (86) эквивалентной системой скалярных равенств
(91)
Из этой системы линейных уравнений мы можем однозначно определить искомые коэффициенты и подставить полученные значения в (88). Это исключение из (88) и (91) можно провести в симметричной форме. Для этого перепишем (88) и (91) так:
Поскольку эта система из уравнений с неизвестными имеет ненулевое решение , то определитель этой системы должен равняться нулю:
. (92)
Отсюда мы определяем , предварительно транспонируя определитель (92) относительно главной диагонали:
, (93)
где постоянный множитель определяется формулой (89) и отличен от нуля.
Тождество (93) и представляет собой преобразование Крылова. В определителе Крылова, стоящем в правой части этого тождества, входит только в элементы последнего столбца; остальные же элементы этого определителя от не зависят.
Замечание. В регулярном случае все пространство является циклическим (относительно оператора ). Если в качестве базиса выбрать векторы , то в этом базисе оператору соответствует матрица , имеющая естественную нормальную форму
. (94)
Переход от основного базиса к базису осуществляется при помощи неособенной преобразующей матрицы
. (95)
3. Особый случай: . В этом случае векторы линейно зависимы, и потому
.
Равенство (93) было выведено при условии . Но обе части этого равенства представляют собой целые рациональные функции от и параметров . Поэтому «из соображений непрерывности» следует, что равенство (93) имеет место и при . Но тогда в определителе Крылова (93) после его раскрытия все коэффициенты окажутся равными нулю. Таким образом, в особом случае формула (93) переходит в тривиальное тождество .
Рассмотрим матрицу, составленную из координат векторов
. (97)
Эта
матрица имеет ранг и первые строк в ней линейно
независимы, последняя же -я строка есть линейная комбинация
первых строк
с коэффициентами 
[см. (83)]. Из координат мы сможем выбрать
такие координат
, чтобы
определитель, составленный из этих координат векторов , был отличен от нуля:
. (98)
(99)
Из этой системы уравнений однозначно определяются коэффициенты многочлена (минимального многочлена вектора ). Совершенно аналогично регулярному случаю (лишь с заменой на и букв буквами ) мы сможем исключить из (85) и (99) и получить следующую формулу для :
. (100)
4. Остановимся на выяснении вопроса, для каких матриц и при каком выборе исходного вектора или, что то же, при каком выборе исходных параметров имеет место регулярный случай.
Мы уже видели, что в регулярном случае
.
Совпадение характеристического многочлена с минимальным многочленом означает, что у матрицы нет двух элементарных делителей с одним и тем же характеристическим числом, т. е. все элементарные делители попарно взаимно просты. В случае, когда – матрица простой структуры, это требование равносильно условию, что характеристическое уравнение матрицы не имеет кратных корней.
Совпадение многочлена с означает, что в качестве вектора выбран вектор, порождающий (при помощи оператора ) все пространство . Такой вектор согласно теореме 2 § 2 всегда существует.
Если же условие не выполняется, то, как бы ни выбрать вектор , мы многочлена не получим, так как полученный по методу Крылова многочлен является делителем , который в рассматриваемом случае не совпадает с многочленом , а является лишь его делителем. Варьируя вектор , мы можем в качестве получить любой делитель .
Полученные выводы мы можем сформулировать в виде следующей теоремы:
Теорема 14. Преобразование Крылова дает выражение для характеристического многочлена матрицы в виде определителя (93) в том и только в том случае, когда выполняются два условия:
1. Элементарные делители матрицы попарно взаимно просты.
2. Исходные параметры являются координатами вектора , порождающего (при помощи оператора , соответствующего матрице ) все -мерное пространство.
В общем же случае преобразование Крылова приводит к некоторому делителю характеристического многочлена . Этот делитель является минимальным многочленом для вектора с координатами ( – исходные параметры в преобразовании Крылова).
5. Покажем, как найти координаты собственного вектора для любого характеристического числа , которое является корнем многочлена , получающегося по методу Крылова.
Вектор будем искать в виде
Подставляя это выражение для в векторное равенство
и используя (101), мы получим:
Отсюда,
между прочим, следует, что , так как равенство в силу (102)
давало бы линейную зависимость между векторами . В дальнейшем мы полагаем . Тогда из (102)
получаем:
Первые
из этих
равенств определяют нам последовательно величины (координаты вектора в «новом» базисе ); последнее же
равенство является следствием из предыдущих и из соотношения 
.
Координаты вектора в исходном базисе могут быть найдены по следующим формулам, которые вытекают из (101):
(104)
Под данной матрицей выписываем строку из координат вектора . Этими числами задаемся произвольно (при одном лишь ограничении: по крайней мере одно из этих чисел отлично от нуля). Под строкой пишем строку , т. е. координаты вектора . Числа , получаются путем последовательного умножения строки на строки данной матрицы . Так, например, , и т. д. Под строкой пишем строку и т. д. Каждая из приписываемых строк, начиная со второй, определяется путем последовательного умножения предыдущей строки па строки данной матрицы.
Над строками данной матрицы выписываем контрольную суммарную строку
.
В данном случае мы имеем регулярный случай, поскольку
.
Определитель Крылова имеет вид
.
Раскрывая этот определитель и сокращая на , найдем:
Обозначим через собственный вектор матрицы , соответствующий характеристическому числу . Числа найдем по формулам (103):
,
, 
, 
.
Контрольное равенство , конечно, удовлетворяется.
Полученные
числа располагаем
в вертикальном столбце параллельно столбцу векторов 
. Помножая столбец на столбец , мы получим первую
координату вектора
в
исходном базисе ;
аналогично получаем . Находим координаты (после сокращения
на 4) вектора .
Аналогично определяем координаты собственного вектора для
характеристического числа .
, (105)
нужно следить за рангом получаемой матрицы с тем, чтобы остановиться на первой [-й сверху] строке, которая является линейной комбинацией предыдущих. Определение ранга связано с вычислением известных определителей. Кроме того, получив определитель Крылова в виде (93) или (100), для раскрытия его по элементам последнего столбца следует вычислить известное число определителей -го порядка [в регулярном случае -го порядка].
Вместо раскрытия определителя Крылова можно определить коэффициенты непосредственно из системы уравнений (91) [или (99)], применяя к этой системе какой-либо эффективный метод решения, например метод исключения. Этот метод можно применить непосредственно к матрице
Обращаем в нуль
элементы -я строка этой матрицы после
преобразования будем иметь вид (а не первоначальный ряд 
) на строки данной
матрицы.
Тогда мы найдем -ю строку в виде
и после вычитания предыдущих строк получим:
.
Рекомендуемое нами небольшое видоизменение метода Крылова (соединение его с методом исключения) позволяет сразу получить интересующий нас многочлен [регулярном случае ] без вычисления каких-либо определителей и решения вспомогательной системы уравнений.
Академик А.Н.Крылов в 1931 году одним из первых предложил довольно удобный метод раскрытия определителя (2).
Суть метода А.Н.Крылова состоит в преобразовании определителя D() к виду
Равенство нулю определителя D() есть необходимое и достаточное условие для того, чтобы однородная система линейных алгебраических уравнений
имела решение х1, х2, …, хn, отличное от нулевого.
Преобразуем систему (2) следующим образом. Умножим первое уравнение на и заменим x1, …,xn их выражениями (2) через x1,…, xn.
Повторяя этот процесс (n-1) раз, мы перейдем от системы (2) к системе
коэффициенты которой будут определятся по рекуррентным формулам
Очевидно, что определитель системы (5) будет иметь вид (1).
Система линейных алгебраических уравнений (5) имеет ненулевое решение для всех значений, удовлетворяющих уравнению D()=0. Таким образом, D1()=0 при всех, удовлетворяющих уравнению D()=0.
Покажем, что
Пусть все корни D() различны. Так как все корни D() являются корнями D1(), то D1() делится на D(). Так как, кроме того, степени D1() и D() одинаковы, то частное должно быть постоянным. Сравнивая коэффициенты при n, получим
В случае, если D() имеет кратные корни, равенство (8) сохраняется.
Рассмотрим теперь коэффициенты bik, определяющие D1(). Введем в рассмотрение векторы Bi с компонентами bi1, bi2, …, bin. Равенства
показывают, что Bi=ABi-1, где A - матрица, транспонированная к данной. Из этого следует, что
Bi=A i-1B1, B1=AB0, (9)
где В0=(1,0,…,0)
Если С0, то уравнения D1()=0 и D()=0 эквивалентны. Если же С=0, то это преобразование ничего не дает. А.Н.Крылов предлагает в этом случае особый прием, рассмотренный ниже. Возьмем в качестве вектора В0 произвольный вектор В0=(bi1,bi2,…,bin) и получим с его помощью по формулам (9) векторы Вi.
Пусть u=b01x1+b02x2+…+b0nxn (10)
где x1,x2,…xn - решения системы (1/). Тогда повторяя прежние рассуждения, получим:
Решая эту систему как систему линейных однородных уравнений с n+1 неизвестными u,x1,x2,…xn, получим, что ненулевое решение возможно в том и только в том случае, когда
Повторяя прежние рассуждения, найдем, что
если С10, то коэффициенты рi характеристического многочлена определяются как отношения где Di - алгебраические дополнения элементов n-i в определителе D().
Но сущность метода Крылова и состоит в том, чтобы находить эти коэффициенты, не подсчитывая миноры.
Воспользуемся теоремой Гамильтона - Кэли о том, что матрица является корнем своего характеристического уравнения, т.е.
(A) n+p1(A)n-1+…+pn-1A+pnE=0, (14)
где рi - коэффициенты характеристического многочлена.
Умножая равенство (14) на b0, получим:
bn+p1bn-1+p2bn-2+…+pn-1b1+pnb0=0 (15)
Это векторное равенство дает систему линейных алгебраических уравнений для определения коэффициентов характеристического многочлена. Определитель этой системы равен С1. Решать полученную систему можно любым из известных методов, например, методом Гаусса.
Можно было бы применить теорему Гамильтона - Кэли и для самой матрицы А, получили бы тогда систему
сn+p1сn-1+p2сn-2+…+pn-1с1+pnс0=0 (15/)
здесь ci=Aic0, c0
Произвольный начальный вектор.
Пример. Пусть матрица A имеет вид:
в качестве вектора В0 возьмем вектор В0=(1,0,0,0). Тогда получим векторы
В1=АВ0, В2=А2В0= АВ1, В3=А3В0=АВ2, В4=А4В0=АВ3:
Система линейных алгебраических уравнений для определения коэффициентов характеристического многочлена имеет вид:
Решив эту систему, получим: р1=-11, р2=7, р3=72, р4=-93. Поэтому характеристический многочлен примет вид:
D()= 4 -113 + 72 +72 -93.
В приведенном примере С10.
В случае, если С=0, такая система не даст возможности определить коэффициенты характеристического уравнения. Матрица А и транспонированная к ней матрица А удовлетворяет своему характеристическому уравнению D(A)=0. Но может оказаться, что существуют многочлены () степени меньше n, для которых также выполняется равенство (А)=(А)=0. Среди таких многочленов имеется единственный многочлен со старшим коэффициентом 1, имеющим наименьшую степень. Этот многочлен называется минимальным. Если минимальный многочлен матрицы не совпадает с характеристическим, то С=0 при любом выборе начального вектора. В этом случае АС0=0 и векторы С0, АС0, …,Аn-1C0 линейно зависимы.
На практике при использовании метода Крылова такая ситуация может возникнуть лишь при особых обстоятельствах.
1.2 Метод Крылова
Метод Крылова основан на свойстве квадратной матрицы М обращать в нуль свой характеристический многочлен. В данной работе матрица М -это матрица коэффициентов технологических связей, которая имеет вид:
Согласно теореме Гамильтона-Кали, всякая квадратная матрица является корнем своего характеристического многочлена и, следовательно, обращает его в нуль. Пусть (1.2.1) характеристический многочлен
Заменяя в выражении величину λ на M, получаем
Взяв произвольный ненулевой вектор У 0 и умножив обе части выражения (1.2.2) на него, получим:
Или в виде
Если эта система имеет единственное решение, то ее корни р 1 , р 2 …..р n , являются коэффициентами характеристического многочлена (1.2.1).
Если известны коэффициенты р 1 , р 2 …..р n , и корни λ 1 , λ 2 ,….λ n характеристического многочлена, то метод Крылова дает возможность найти соответствующие векторы по следующей формуле:
Здесь y (n -1) , y (n -2) , …. y (0) – векторы, использованные при нахождении коэффициентов р 1 , р 2 …..р n методом Крылова, а коэффициенты q ij () определяются по схеме Горнера
q 0i = 1, q ij = λ i q i-1,i +p i (1.2.7)
Для определения собственных чисел матрицы М необходимо решить полученное характеристическое уравнение. Для матрицы М это уравнение будет пятой степени, решать такое уравнение в данной работе будем решать, используя метод касательных или иначе метод Ньютона.
1.3 Метод Ньютона (метод касательных)
Метод Ньютона (также известный как метод касательных) - это итерационный численный метод нахождения корня (нуля) заданной функции. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.
Чтобы численно решить уравнение f (х) = 0 методом простой итерации, его необходимо привести к следующей форме: х = f(х), где f (х) -сжимающее отображение.
Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:
В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:
(1.3.2)
С учётом этого функция определяется выражением
(1.3.3)
Эта функция в окрестности корня осуществляет сжимающее отображение, и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:
(1.3.4)
По теореме Банаха последовательность приближений стремится к корню уравнения .
Рисунок 1.1- Графическое представление метода Ньютона
Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.
Достоинства метода Ньютона:
1) если минимизируемая функция является квадратической, то метод позволит найти минимум за один шаг;
2) если минимизируемая функция относится к классу поверхностей вращения, то метод также обеспечивает сходимость за один шаг;
3) если функция несимметрична, то метод не обеспечивает сходимость за конечное число шагов. Но для многих функций достигается гораздо более высокая скорость сходимости, чем при использовании других модификаций метода наискорейшего спуска.
Использование метода Крылова и метода Ньютона приведены в приложениях. Реализация методов производилась в среде МаthСАD и VB.Net.
На разработку и материальные затраты. Таким образом, цель дипломного проектирования – разработка программного комплекса для моделирования радиолокационной обстановки на персональном компьютере, позволяющего моделировать радиолокационную обстановку по заданным параметрам, создавать выходной файл, содержащий рассчитанную модель, использовать полученный файл для проверки реальных устройств обработки...
