Системы числовых уравнений в арифметических пространствах

Московский государственный  университет леса

 

 

 

 

Курсовая работа по функциональному анализу

на тему: «Системы числовых уравнений в арифметических пространствах».

 

 

 

 

 

 

 

 

 

Выполнил: студент Гераськин А.В.

Группа ПМ-31

Руководитель: доцент кафедры высшей

математики МГУЛ, Галканов А.Г.

 

 

Москва 2013

Содержание.

• Введение………………………………………………….…….3
• Понятия, связанные с системой и совокупностью

уравнений………………………………………………….…...4

• Методы решения линейных систем уравнений…………......8
• Прямые методы ……………………………...……………….…9
• Итерационные методы………………………………………...17
• Методы решения нелинейных систем уравнений……….…21
• Заключение…………………………………………………....26

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

В начале работы хотелось бы определить несколько понятий, которые пригодятся нам в дальнейшем. Эти понятия были взяты из книги А.Г.Галканова  «Числовые уравнения и тождества в понятиях, теоремах, методах, задачах и решениях».

Уравнение – аналитическая  запись задачи о разыскании значений аргументов, при которых значения двух данных функций равны. Решить уравнение  означает найти множество всех его  решений(корней) или доказать, что корней нет.

Определение 1.

Если , то предикат (1) называется числовым уравнением.

При этом:

• X называется множеством задания уравнения.
• x называется неизвестным уравнения.
• f и g соответственно левой и правой частью уравнения.

Определение 2.

Если (1) есть уравнение и , то число называется корнем (или решением) уравнения (1) на множестве X.

Определение 3.

Линейное уравнение —  это алгебраическое уравнение, у  которого полная степень составляющих его многочленов равна 1.

В общем виде:

 

В канонической форме:

 

Определение 4.

Если  т.е. существует последовательность , сходящаяся к стационарной последовательности {x^*} и разность двух сходящихся числовых последовательностей {} и {} есть бесконечно малая, то каждое число , начиная с номера l+1, называется приближённым корнем уравнения (1) с погрешностью δ в смысле близости по значениям аргумента и с погрешностью ε в смысле близости по значениям функций f и g.

При этом числа x₁, x₂,…,x_n,… называются последовательными приближениями к искомому корню, а δ и ε – их погрешностями.

Определение 5.

Множество всех упорядоченных  совокупностей по n чисел (х₁,х₂,...,х_n) называется арифметическим n-мерным пространством ℝⁿ, где n - размерность пространства.

 

На множестве естественным образом вводятся операции сложения и умножения на числа. Если , то по определению для числа :

 , a

Отметим свойства введенных  операций(X,Y,Z:

• α(X+Y)=αX+αY
• (αβ)X=α(βX)
• 1*X=X

 

 

Понятия, связанные  с системой и совокупностью уравнений.

Пусть – это упорядоченный набор из n(n≥2) действительных чисел X≠. Рассмотрим n – местный предикат

 , (2)

где - заданные функции своих аргументов, определённые и непрерывные в области X, , m ≥ 2.

Определение 6.

Если

 

то предикат (2) называется системой (числовых) уравнений на множестве  X.

Если (2) есть система уравнений, то n называется числом неизвестных, m – числом уравнений и вместо (2) применяется наиболее распространенная запись

                                                               (3)

где знак { принято считать знаком системы уравнений (или знаком совместных утверждений).

Определение 7.

Упорядоченный набор , такой, что

,

называется решением системы  уравнений (3).

Определение 8.

Множество

 называется  множеством решений системы уравнений  (3).

Пример 1.

S={(1,1),(5,3)} является множеством решений системы уравнения

Определение 9.

Две системы уравнений, называются эквивалентными или равносильными, если их множества задания и множества  решений соответственно равны.

Определение 10.

Система уравнений (3) называется совместной, если она имеет хотя бы одно решение, иначе – несовместной.

Определение 11.

Система (3) называется однородной, если все её свободные члены равны  нулю (b₁ = b₂ = … = b_m = 0), иначе — неоднородной.

Определение 12.

Система уравнений (3) называется определённой, если она имеет единственное решение, иначе – неопределённой.

Как  и уравнение, всякая система уравнений(3):

• либо имеет единственное решение;
• либо имеет множество решений;
• либо не имеет решения.

 

Пусть

 

 

 

                      ………………………,

 

где все уравнения рассматриваются на одном и том же непустом множестве X.

Определение 13.

Некоторое число  называется решением совокупности уравнений (3₁)-(3_n), если x^* есть решение, по меньшей мере, одного из уравнений (3₁)-(3_n):.

При этом пишут 

В соответствии с этим саму совокупность уравнений обозначим

  , а множество  её корней - .

Определение 14.

Если , т.е. каждое решение уравнения (3₀) является решением совокупности уравнений (3₁)-(3_n) и всякое решение совокупности уравнений (3₁)-(3_n) является решением уравнения (3₀), то уравнение (3₀) называется равносильным совокупности уравнений (3₁)-(3_n).

При этом пишут 

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

Определение 15.

Если в (3) все функции f_k ,g_k являются линейными, то (3) называется линейной системой, иначе, т.е. хотя бы одна из функций f_k ,g_k нелинейная – нелинейной системой уравнений.

Наиболее изученными являются системы линейных алгебраических уравнений (СЛАУ):

                             (4),

где a_i,j,b_j – заданные действительные числа, При m=n (4) называется квадратной, иначе прямоугольной.

Также СЛАУ можно записать в матричной форме:

                           ,

или Ax=b, где A – матрица системы, x – столбец неизвестных, b – столбец свободных членов. Если к матрице A приписать справа столбец свободных членов, то получившаяся матрица называется расширенной.

Наряду с системой уравнений (3) рассматриваются и системы  неравенств:

,

 

или смешанные системы  вида:

 

 

Методы решений  линейных систем уравнений.

Существует достаточно много  методов решения систем уравнений, которые можно разделить на 2 вида:

• Прямые (точные) - методы позволяют найти решение за определённое количество шагов, к ним относятся:
• Метод Гаусса
• Метод Гаусса — Жордана
• Метод Крамера
• Матричный метод
• Метод прогонки (для трёхдиагональных матриц)
• Разложение Холецкого или метод квадратных корней (для положительно-определённых симметричных и эрмитовых матриц)
• Метод вращений.
• Итерационные методы - основаны на использовании повторяющегося процесса и позволяют получить решение в результате последовательных приближений, к ним относятся:
• Метод Якоби (метод простой итерации)
• Метод Гаусса — Зейделя
• Метод релаксации
• Многосеточный метод
• Метод Монтанте
• Метод Абрамова (пригоден для решения небольших СЛАУ)
• Метод квази-минимальных невязок (QMR)

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

 

Прямые методы решения систем уравнений.

Рассмотрим несколько  основных методов решения СЛАУ.

Метод Гаусса.

Хотя в настоящее время  данный метод повсеместно называется методом Гаусса, он был известен и до К. Ф. Гаусса. Первое известное  описание данного метода — в китайском  трактате «Математика в девяти книгах», составленном между I в. до н.э. и II в. н. э.

Метод Гаусса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Это  метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений  приводится к равносильной системе  треугольного вида, из которой последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.

К достоинствам данного метода можно отнести:

• Для матриц ограниченного размера менее трудоёмкий по сравнению с другими методами.
• Позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение.
• Позволяет найти максимальное число линейно независимых уравнений — ранг матрицы системы.

 

 

Алгоритм:

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

 

 

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

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

,

Далее начинается обратный ход, при котором последовательно, начиная с x_n, находим все x, для этого:

 

Таким образом, алгоритм решения СЛАУ методом Гаусса можно разделить на два этапа:

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

Пример:

Решить систему:

 

Решение:

Для решения данной системы  вначале обнулим коэффициенты при x₁ во 2 и 3 строчках системы, для этого вычтем из них первую строчку, делённую на 2 и 4 соответственно:

 

Теперь обнулим коэффициент  в 3 строчке, для этого вычтем из неё 2 строчку, делённую на 2:

 

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

Из 3-го уравнения имеем:  ;

из 2-го уравнения: ;

из 1-го:.

Таким образом, исходная система решена.

К недостаткам такого метода можно отнести то, что для матриц большого объёма данный метод очень  трудоёмкий, а также его большую  погрешность возникающую, в случае если ведущие элементы малы. Поэтому обычно используется другой вариант метода Гаусса – метод Гаусса с выбором главного элемента.

Путем перестановки строк, а  также столбцов с соответствующей перенумерацией коэффициентов и неизвестных добиваются выполнения условия:

, j = i+1,i+ 2, …, m;

т.е. осуществляется выбор  первого главного элемента. Переставляя  уравнения так, чтобы в первом уравнении коэффициент a₁₁ был максимальным по модулю. Разделив первую строку на главный элемент, как и прежде, исключают x₁ из остальных уравнений. Затем для оставшихся столбцов и строк выбирают второй главный элемент и т.д.

Рассмотрим применение метода Гаусса с выбором главного элемента на примере следующей системы  уравнений:

 

 В первом уравнении коэффициент при x₁ =0, во втором  1 и в третьем   -2, т.е. максимальный по модулю коэффициент в третьем уравнении.

 

Поэтому переставим третье и первое уравнение:

 

 

Исключим  x₁ из второго и третьего уравнений с помощью первого. Во втором уравнении исключать не надо. Для исключения из третьего уравнения умножим первое на 0.5 и сложим с третьим:

 

 

Рассмотрим второе и третье уравнения. Максимальный по модулю элемент  при  x₂  в третьем. Поэтому поместим его на место второго:

 

 

Исключим  x₂  из третьего уравнения. Для этого умножим второе на -0.5 и сложим с третьим:

 

 

Выполняя обратный ход, получим  результат:

 

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

Метод  QR-разложений.

В настоящее время, кроме  метода Гаусса, известно много прямых методов решения систем линейных алгебраических уравнений. Большинство  этих методов основано на переходе от исходной системы Ax = b к новой системе Bx = d , решаемой проще исходной. Этот переход производится путем умножения исходной системы на некоторую матрицу C, которая выбирается из условий, чтобы эта матрица вычислялась не слишком сложно, а само умножение не сильно портило систему, то есть не сильно изменяло ее число обусловленности. Этим условиям удовлетворяют методы вращений и отражений. Оба метода позволяют получить представление матрицы A в виде произведения ортогональной матрицы Q на верхнюю треугольную матрицу R: