3107

Нелинейные уравнения и способы их решения

Шпаргалка

Математика и математический анализ

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

Русский

2012-10-24

1.97 MB

115 чел.

  1.  Метод Гаусса, особенности реализации.

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

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

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

Метод Гаусса требует порядка O(n3) действий.

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

  1.  Нахождение обратной матрицы. Вычисление определителя.

Обратная матрица — такая матрица A−1, при умножении на которую исходная матрица A даёт в результате единичную матрицу E: 

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

Система состоит из n уравнений с n переменными

Эту систему можно записать в матричном виде

Если матрица коэффициентов  невырожденная, то существует обратная ей матрица  и система имеет единственное решение,,,.

  1.  Сравнение правила Крамера и метода Гаусса по числу операций.

Проблема численного решения линейных уравнений интересует математиков уже несколько столетий. Первые математические результаты появились в XVIII веке. В 1750 году Г. Крамер (1704-1752) опубликовал свои труды по детерминантам квадратных матриц и предложил алгоритм нахождения обратной матрицы, известный как правило Крамера. Гаусс в 1809 году опубликовал работу, посвященную движению небесных тел, в которой был изложен метод для решения линейных систем, известный как метод исключения.

В 40-х годах XX века с появлением компьютеров сильно возрос интерес к численным методам. Тогда же началось активное исследование существующих методов для их реализации на ЭВМ и предпринимались активные попытки увеличить их точность.

Вплоть до 80-х годов решение вычислительных задач было ограничено ресурсами ЭВМ, поэтому особое значение придавалось экономичности алгоритмов.

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

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

Пример. Если вычислять определитель непосредственно по его определению, то нужно выполнить (n - 1)n! умножений и n! сложений. Положим n = 15 и возьмем ЭВМ с производительностью 106 умножений в секунду. Тогда вычисление только одного определителя потребует 14 " 15! ї 1,8 " 1013 умножений, в результате чего на вычисление решения уйдет около 10 лет непрерывной работы ЭВМ. Вместе с тем для решения такой системы аналогичной ЭВМ потребуется примерно 0,002 секунд с использованием метода Гаусса. Для реализации метода Гаусса требуется примерно (2/3)n3 арифметических операций, причем основное число этих действий совершается на этапе прямого хода.

  1.  Обзор способов решения нелинейных уравнений. Отделение корней: графический метод и аналитический метод.

Уравнение типа F(x)=0 или x=f(x) называется нелинейным. Решить уравнение это значит найти такое x, при котором уравнение превращается в тождество. В общем случае уравнение может иметь 0; 1; 2;...∞ корней. Рассмотренные ниже численные методы решения нелинейных уравнений позволяют находить один корень на заданном интервале [a,b]. При этом на интервале должен существовать только один корень. Рассмотрим несколько методов решения нелинейных уравнений.

Метод перебора. При решении нелинейного уравнения методом перебора задаются начальное значение аргумента x=a и шаг h, который при этом определяет и точность нахождения корней нелинейного уравнения. Пока выполняется условие F(x)*F(x+h)>0 аргумент x увеличиваем на шаг h (x=x+h). Если произведение F(x)*F(x+h) становится отрицательным, то на интервале [x,x+h] существует решение уравнения. Пока F(x)∙F(x+h)>0 → x=x+h

Метод половинного деления. При решении нелинейного уравнения методом половинного деления задаются интервал [a,b], на котором существует только одно решение, и желаемая точность ε. Затем определяется середина интервала с=(а+b)/2 и проверяется условие F(a)∙F(c)<0. Если указанное условие выполняется, то правую границу интервала b переносим в среднюю точку с (b=c). Если условие не выполняется, то в среднюю точку переносим левую границу(a=c). Деление отрезка пополам продолжается пока |b-a|>ε.

Пока |b-a|>ε → c=(a+b)/2 →F(a)∙F(c)<0

Метод хорд. При решении нелинейного уравнения методом хорд задаются интервал [a,b], на котором существует только одно решение, и точность ε. Затем через две точки с координатами (a,F(a)) и (b,F(b)) проводим отрезок прямой линии (хорду) и определяем точку пересечения этой линии с осью абсцисс (точка c). Если при этом F(a)∙F(c)<0, то правую границу интервала переносим в точку с (b=c). Если указанное условие не выполняется, то в точку c переносится левая граница интервала (а=с). Поиск решения прекращается при достижении заданной точности |F(c)|< ε. Для определения точки пересечения хорды с осью абсцисс воспользуемся следующей формулой .  Пока |F(c)|>ε   F(a)∙F(c)<0

Метод касательных. При решении нелинейного уравнения методом касательных задаются начальное значение аргумента x0 и точность ε. Затем в точке(x0,F(x0)) проводим касательную к графику F(x) и определяем точку пересечения касательной с осью абсцисс x1. В точке (x1,F(x1)) снова строим касательную, находим следующее приближение искомого решения x2 и т.д. Указанную процедуру повторяем пока |F(xi)| > ε. Для определения точки пересечения (i+1) касательной с осью абсцисс воспользуемся следующей формулой . Условие сходимости метода касательных F(x0)∙F''(x0)>0. Пока |F(x)|> ε

Метод хорд-касательных. Если в методе касательных производную функции F'(xi) заменить отношением конечных приращений, то получаем расчетную формулу для метода хорд-касательных . Порядок выполнения вычислений в данном методе аналогичен рассмотренному ранее.

Метод итераций. При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x). Задаются начальное значение аргумента x0 и точность ε. Первое приближение решения x1 находим из выражения x1=f(x0), второе - x2=f(x1) и т.д. В общем случае i+1 приближение найдем по формуле xi+1 =f(xi). Указанную процедуру повторяем пока |f(xi)|>ε. Условие сходимости метода итераций |f'(x)|<1. Пока |f(xi)|> εxi+1 =f(xi)

Следовательно, прежде чем применять тот или иной итерационный метод, мы должны определить некоторую область пространства G, которой будет принадлежать искомое  решение системы (1).  Эта задача называется отделением корней. 

Аналитический способ

Теорема

  1.  " Если функция F(x), определяющая уравнение  F(x)=0, на концах отрезка [a;b] принимает значения разных знаков, т.е. F(a)*F(b)<0 (3), то на этом отрезке содержится, по крайней мере, один корень уравнения"[4].
  2.  "Если функция F(x) строго монотонна, то корень на [a,b] единственный (F’(a)*F’(b)>0 (4)) .

Для отделения корней аналитическим способом выбирается отрезок [A;B], на котором находятся все интересующие вычислителя корни уравнения. Причем на отрезке  [A;B] функция F(x) определена, непрерывна и F(a)*F(b)<0. Требуется указать все частичные отрезки  [a;b], содержащие по одному корню.

Будем вычислять значение функции  F(x), начиная с точки x=A, двигаясь вправо с некоторым шагом h. Если F(x)*F(x+h)<0, то на отрезке [x;x+h]  существует корень:"[1]

Для отделения корней аналитическим способом выбирается отрезок [A;B], на котором находятся все интересующие вычислителя корни уравнения. Причем на отрезке  [A;B] функция F(x) определена, непрерывна и F(a)*F(b)<0. Требуется указать все частичные отрезки  [a;b], содержащие по одному корню.

Будем вычислять значение функции  F(x), начиная с точки x=A, двигаясь вправо с некоторым шагом h. Если F(x)*F(x+h)<0, то на отрезке [x;x+h]  существует корень:"[1]

Если F(xk)=0, xk-точный корень. (5)

Графический способ отделения корней

Отделение корней во многих случая можно произвести графически, "учитывая что действительные корни уравнения F(x)=0 (1) - это есть точки пересечения графика функции y=F(x) с осью абсцисс y=0, нужно построить график функции y=F(x) на оси OX отметить отрезки, содержащие по одному корню. Но часто для упрощения построения графика функции y=F(x) исходное уравнение (1) заменяют равносильным ему уравнением f1(x)=f2(x) (2). Далее строятся графики функций y1=f1(x) и y2=f2(x) , а затем по оси OX отмечаются отрезки, локализующие абсциссы точек пересечения двух графиков"[1].

  1.  Решение нелинейных уравнений методом половинного деления.

Пусть корень уравнения (1) отделен на отрезке [a;b]. Требуется найти значение корня с точностью ε.

"Процедура уточнения положения корня заключается в построении последовательности вложенных друг в друга отрезков, каждый из которых содержит корень уравнения. Для этого находится середина текущего интервала неопределенности (6): 

В качестве следующего интервала неопределенности из двух возможных выбирается тот, на концах которых функция F(x)=0 имеет разные знаки"[8]. "Точность будет достигнута, если:  

Корень уравнения вычисляется по формуле x=(an+bn)/2 (7)"[1].

  1.  Решение нелинейных уравнений методом касательных (Ньютона).

" В отличие от метода хорд, в методе касательных вместо хорды на каждом шаге проводится касательная к кривой y=F(x) при x=xn  и ищется точка пересечения касательной с осью абсцисс.

Формула для (n+1) приближения имеет вид (10):

Если F(a)*F"(a)>0, x0=a, в противном случае x0=b.

Итерационный процесс продолжается до тех пор, пока не будет обнаружено, что:

  1.  Теорема о сходимости метода Ньютона. Способы подбора начальной точки итерационного процесса.

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

x(k+1) = x(k) - f(x(k))/f '(x(k))

Следовательно,

x(k+1) = φ(x(k)), где φ(x) = x - f(x) / f '(x)

Проверим следующее условие теоремы о сходимости метода простой итерации: |φ '(x)| ≤ q < 1. (2.16)

В случае метода Ньютона имеем: φ '(x) = 1 - [(f '(x))2 - f ·f ''] / (f ')2

Пусть корень X уравнения f(x)=0 имеет кратность p ≥ 1. Тогда в достаточно малой окрестности корня X имеет место представление:

f(x) ≈ a(x-X) p 

Следовательно

 φ '(x) = f ·f ''/(f ') 2 ≈ a(x-X) pa·p(p-1)(x-X) p-2/[a·p(p-1)(x-X) p-1] 2 = (p-1)/p < 1

Таким образом в некоторой окрестности корня X условие (2.16) выполнено с константой q < 1.

ЗАМЕЧАНИЕ 2.3

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

2) При вычислении корня уравнения с точностью ε по методу Ньютона условием окончания итераций может служить: | x(k+1) - x(k) | ≤ ε

  1.  Решение нелинейных уравнений методом простой итерации.

Пусть есть функция .

Требуется найти корень этой функции: такой x при котором

Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций.

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

Геометрическая интерпретация

Рассмотрим график функции . Это озночает, что решение уравнения и - это точка пересечения с прямой :

И следующая итерация - это координата x пересечения горизонтальной прямой точки с прямой .

Из рисунка наглядно видно требование сходимости . Чем ближе производная к 0, тем быстрее сходится алгоритм. В зависимости от знака производной вблизи решения приближения могут строится по разному. Если , то каждое следующее приближение строится с другой стороны от корня:

9.Теоремы о сходимости метода простой итерации.

Метод сходится, если при последовательность {} имеет предел.

Обозначим окрестность точки радиуса , то есть .

Теорема 1. Если липшиц-непрерывна с константой на , то есть выполняется ,при этом если также выполнено , то уравнение имеет единственное решение на и метод простой итерации сходится к решению при любом выборе начального приближения .Так же справедлива оценка: , где - точное решение.

Из оценки видно, что метод линеен. Пусть непрерывно дифференцируема на , тогда из теоремы вытекают следующие утверждения:

Следствие 1. Если для , выполнено , и , тогда уравнение имеет единственное решение на и метод простой итерации сходится к решению.

Следствие 2. Если уравнение имеет решение , непрерывно дифференцируема на и . Тогда существует такое, что на уравнение не имеет других решений и метод простой итерации сходится к решению при .

  1.  Решение нелинейных уравнений методом Рыбакова.

Для дальнейшего нам понадобится теорема Лагранжа. Приведем(напомним) ее формулировку:

Если функция f является непрерывной на замкнутом отрезке  [a,b]  и существует конечная производная на открытом отрезке(a,b),то обязательно найдется точка a<с<b такая, что будет выполняться равенство:

f(b)-f(a)=f (c)(b-a).

Геометрический смысл этой теоремы заключается в том, что найдетсякасательная,  параллельная прямой, проходящей через точки (a, f(a)) и (b, f(b)).

Теорема. Если для функции  f(x) существует конечная производная на отрезке, то для метода Рыбакова  всегда будет выполняться неравенство xn < x, где f(x)=0. Другими словами xn  не “перепрыгнет” через корень х и, таким образом, последовательно будут найдены все корни.

Доказательство. Предположим что число x является корнем уравнения f(x)=0 и  выполняется неравенство xn <x< xn+1,  .   По теореме Лагранжа существует такая точка с, что  a xn<с<xb и выполняется равенство  |f(x)-f(xn)|= |f (c) (x- xn)|. Так как a<с<b, то значит и |f(c)|<M. Учтем,   что f(x)=0 и xn<x, а значит |(x- xn)|= (x- xn).

Поэтому справедливо неравенство:  |f(xn)|= |f (c) | | (x- xn)|=|f(c) |(x- xn)<M(x- xn). Так как M>0, то отсюда  |f(xn)|/M<(x- xn)  и окончательно получим  x> xn+|f(xn)|/M =xn+1 .Таким образом пришли к противоречию  x> xn+1 с первоначальным предположением  xn <x< xn+1 .

  1.  Доказательство сходимости метода Рыбакова.

Теорема. Если для функции  f(x) существует конечная производная на отрезке, то для метода Рыбакова  всегда будет выполняться неравенство xn < x, где f(x)=0. Другими словами xn  не “перепрыгнет” через корень х и, таким образом, последовательно будут найдены все корни.

Доказательство. Предположим что число x является корнем уравнения f(x)=0 и  выполняется неравенство xn <x< xn+1,  .   По теореме Лагранжа существует такая точка с, что  a xn<с<xb и выполняется равенство  |f(x)-f(xn)|= |f (c) (x- xn)|. Так как a<с<b, то значит и |f(c)|<M. Учтем,   что f(x)=0 и xn<x, а значит |(x- xn)|= (x- xn).

Поэтому справедливо неравенство:  |f(xn)|= |f (c) | | (x- xn)|=|f(c) |(x- xn)<M(x- xn). Так как M>0, то отсюда  |f(xn)|/M<(x- xn)  и окончательно получим  x> xn+|f(xn)|/M =xn+1 .Таким образом пришли к противоречию  x> xn+1 с первоначальным предположением  xn <x< xn+1 .

  1.  Решение систем нелинейных уравнений методом Ньютона.

Систему уравнений, состоящую из нелинейных алгебраических и трансцендентных уравнений, будем называть системой нелинейных уравнений (СНУ). В общем виде такую систему записывают следующим образом: 

Решением системы является вектор переменных х, обращающий каждое уравнение системы в тождество.

У системы нелинейных уравнений определить количество векторов-решений заранее невозможно. Система как не иметь решений вообще, так и иметь одно, два или даже бесконечное множество решений.

В связи с этим, методы численного решения СНУ требуют, чтобы начальное приближение было задано достаточно близко к искомому решению. Начальное приближение определяют либо графически (если это возможно), либо грубой прикидкой.

Метод ньютона иначе называют методом последовательных приближений.

Предположим, что найдено k-ое приближение одного из изолированных корней векторного уравнения: .

Тогда точный корень можно представить в виде (3), где .

Предположим, что функция f(x) непрерывно дифференцируема в некоторой выпуклой области, содержащей x и x(k). Разложим левую часть уравнения по степеням вектора (значения которого невелики) в ряд Тейлора, причем ограничимся только линейными членами ряда: (5).

В формуле (5) под производной следует понимать матрицу Якоби системы функций f относительно переменных x, т.е.

Следовательно, формула для получения приближений (формула Ньютона), выглядит так:  

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

  1.  Аппроксимация функций: обзор основных методов.

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

Интерполяционный многочлен Лагранжа

"Пусть некоторая функция y=f(x) задана таблично:

Где x0, x1,..., xn - узлы интерполяции. Причем, расстояние между узлами интерполяции произвольное.

В интерполировании находят значение функции в заданной точке xk, принадлежащей отрезку [x0;xn], но xk не совпадает ни с одним узлом интерполяции (xk не равно x0, x1,...,xn.)

Интерполяционную функцию подбирают из определенного класса функций. Часто такую функцию находят в виде интерполяционного многочлена Fn(x).

В качестве интерполяционного многочлена будем рассматривать интерполяционный многочлен Лагранжа Ln(x).

Многочлен Лагранжа строят следующим образом (24):

Ln(x)=l0(x)+l1(x)+l2(x)+...+ln(x), где li(x) вычисляется по следующей формуле (25):

Ньютон

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

Перепишем полином Лагранжа в другом виде:

где - полиномы Лагранжа степени i ≤ n.

Пусть . Этот полином имеет степень i и обращается в нуль при .

Поэтому он представим в виде: где - коэффициент при . Так как не входит в , то совпадает с коэффициентом при в полиноме .

Таким образом из определения получаем:

где

Препишем формулу в виде Рекуррентно выражая пролучам окончательную формулу для полинома:

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

  1.   Численное дифференцирование. Вычисление производных с помощью  конечных разностей. 

  1.  Интерполяция с помощью многочлена Лагранжа. Оценка погрешности интерполяции см вопрос 13
  2.  Интерполяция с помощью многочлена Ньютона. Оценка погрешности интерполяции. См вопр 13

 

А также другие работы, которые могут Вас заинтересовать

5134. Общая патология клетки. Повреждение клетки 120 KB
  Общая патология клетки. Повреждение клетки: Нарушение функционирования клетки, которое сохраняется после удаления повреждающего агента Генетически детерминированные или приобретенные изменения метаболизма, физико-химических параметров, к...
5135. Кадровая политика на предприятии 71.5 KB
  Создание конкурентоспособного предприятия всегда связано с людьми, которые работают на предприятии. Организация возможностей фирмы заключена в новых методах управления и зависит от конкретных людей, знаний, компетенции, квалификации, дисциплины, мот...
5136. Формы расчетов, применяемые при осуществлении внешнеэкономической деятельности 24.59 KB
  Формы расчетов, применяемые при осуществлении внешнеэкономической деятельности Внешнеэкономическая деятельность неразрывно связана с необходимостью определения форм расчетов. Под формами расчетов понимаются сложившиеся в международном коммерческом о...
5137. Принципы формирования кадровой политики. Кадровая политика и стратегия управления персоналом 59.5 KB
  Принципы формирования кадровой политики. Кадровая политика и стратегия управления персоналом Кадровая политика – главное направление в работе с кадрами, набор основополагающих принципов, которые реализуются кадровой службой предприятия. В этом ...
5138. Структура механизмов. Классификация кинематических пар 330.69 KB
  Структура механизмов. Классификация кинематических пар Кинематические пары (КП) классифицируются по следующим признакам: 1) по виду места контакта (места связи) поверхностей звеньев: - низшие, в которых контакт звеньев осуществляется по плоскости ил...
5139. Методология системного анализа 100.5 KB
  Принцип системности. Система. Основные понятия и определения Основным исходным положением системного анализа – как научной дисциплины является принцип системности, который можно воспринимать в качестве философского принципа, выполняющего ...
5140. Древнегреческая натурфилософия 97 KB
  Древнегреческая натурфилософия. Вопрос 1 Философия милетелей, Пифагора и Гераклита. Мудрость в том, чтобы знать все как одно (Гераклит). Периоды и проблемы Античной философии. Условно выделяют пять периодов античной философии. Во-первых, натурфилософ...
5142. Задачи и технические средства спутниковой геодезии 1.15 MB
  Задачи и технические средства спутниковой геодезии Теоретические и прикладные задачи спутниковой геодезии. Общая характеристика спутниковых систем, обеспечивающих геодезические измерения и наблюдения. Факторы, влияющие на результат...