Смекни!
smekni.com

Разработка системы для оценки перспективности производственных направлений на предприятии (стр. 2 из 3)

(1.2.1)

Заменяя в выражении величину λ на M, получаем

(1.2.2)

Взяв произвольный ненулевой вектор У0 и умножив обе части выражения (1.2.2) на него, получим:

(1.2.3)

Положим

(1.2.4)

Тогда

(1.2.5)

Или в виде

Если эта система имеет единственное решение, то ее корни р1, р2…..рn, являются коэффициентами характеристического многочлена (1.2.1).

Если известны коэффициенты р1, р2…..рn, и корни λ1 , λ2 ,….λnхарактеристического многочлена, то метод Крылова дает возможность найти соответствующие векторы по следующей формуле:

,
(1.2.6)

Здесь y(n-1), y(n-2), …. y(0) – векторы, использованные при нахождении коэффициентов р1, р2…..рnметодом Крылова, а коэффициенты qij(

) определяются по схеме Горнера

q0i = 1, qij = λiqi-1,i+pi (1.2.7)

Для определения собственных чисел матрицы М необходимо решить полученное характеристическое уравнение. Для матрицы М это уравнение будет пятой степени, решать такое уравнение в данной работе будем решать, используя метод касательных или иначе метод Ньютона.

1.3 Метод Ньютона (метод касательных)

Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.

Чтобы численно решить уравнение f (х) = 0 методом простой итерации, его необходимо привести к следующей форме: х = f(х), где f (х) -сжимающее отображение.

Для наилучшей сходимости метода в точке очередного приближения

должно выполняться условие
. Решение данного уравнения ищут в виде
, тогда:

(1.3.1)

В предположении, что точка приближения «достаточно близка» к корню

, и что заданная функция непрерывна
, окончательная формула для такова:

(1.3.2)

С учётом этого функция

определяется выражением

(1.3.3)

Эта функция в окрестности корня осуществляет сжимающее отображение, и алгоритм нахождения численного решения уравнения

сводится к итерационной процедуре вычисления:

(1.3.4)

По теореме Банаха последовательность приближений стремится к корню уравнения

.

Рисунок 1.1- Графическое представление метода Ньютона

Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.

Достоинства метода Ньютона:

1) если минимизируемая функция является квадратической, то метод позволит найти минимум за один шаг;

2) если минимизируемая функция относится к классу поверхностей вращения, то метод также обеспечивает сходимость за один шаг;

3) если функция несимметрична, то метод не обеспечивает сходимость за конечное число шагов. Но для многих функций достигается гораздо более высокая скорость сходимости, чем при использовании других модификаций метода наискорейшего спуска.

Использование метода Крылова и метода Ньютона приведены в приложениях. Реализация методов производилась в среде МаthСАD и VB.Net.

1.4 Метод Гаусса для решения систем уравнений

Метод Гаусса - классический метод решения системы линейных алгебраических уравнений. Состоит в постепенном понижении порядка системы и исключении неизвестных.

Пусть исходная система выглядит следующим образом

(1.4.1)

Матрица A называется основной матрицей системы, b — столбцом свободных членов.

Тогда согласно свойству элементарных преобразований над строками основную матрицу этой системы можно привести к ступенчатому виду (эти же преобразования нужно применять к столбцу свободных членов)

При этом будем считать, что базисный минор (ненулевой минор максимального порядка) основной матрицы находится в верхнем левом углу, то есть в него входят только коэффициенты при переменных

.

Тогда переменные

называются главными переменными. Все остальные называются свободными.

Если хотя бы одно число

, где i > r, то рассматриваемая система несовместна.

Пусть,

для любых i > r.

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом

, где
- номер строки)

(1.4.2)

где

Если свободным переменным системы (1.4.2) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1.4.1), то по теореме об эквивалентности при элементарных преобразованиях системы (1.4.1) и (1.4.2) эквивалентны, то есть множества их решений совпадают.

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.

На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получавшуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.

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