Комбинированный метод хорд и касательных алгоритм. Комбинированный метод хорд и касательных

Комбинированный метод, сочетающий метод хорд и метод касательных, является наиболее эффективным по числу итераций, необходимых для достижения заданной точности. На каждой итерации, начиная с первой, находим x по методу хорд и z по методу касательных. Исходные данные для первой итерации определяются так, как это делается в каждом из составляющих методов.

Расчетные формулы:

Процесс нахождения приближенного корня прекращается, когда выполняется условие:

Приближенное значение корня вычисляют по формуле:

Реализация метода в MS Excel

Адрес клетки
	A1:F9 - метод хорд
	A1:F9– метод касательных
	Комбинированный метод
	Метод хорд
	Метод касательных
	ЕСЛИ(ABS(B7-I7)<=2*0,0001; "|x-z|<=2ε";ABS(B7-I7))
	EXP(COS(M13)^2)-3*SIN(0,8*M13)+0,5

Вид листа MS Excel:

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

Реализация метода в MS Excel с использованием функции Поиск решения

Порядок заполнения клеток листа:

Вид листа MS Excel:

Переходим на страницу «Данные». Активизируем команду «Поиск решения».

После открытия диалогового окна «Поиск решения» устанавливаем значения параметров:

Выполняем щелчок по кнопке Выполнить . Открывается диалоговое окно «Результаты поиска решения»:

Щелкаем по кнопке ОК .

Вид листа MS Excel

Решение получено. Окончательно имеем х=0,8980, f(x)=-0,0000001.

Реализация решения задачи в MatLab

Для решения данной задачи можно использовать функции:

fzero – значение действительного корня уравнения;

roots – значения действительных и комплексных корней многочлена.

Решим уравнение e cos 2 ( x ) -3· sin (0,8· x )+0,5=0 . Сначала введем функцию, используяinline . Затем вызовемfzero, указав в качестве начального значения 0. Для правильного выбора начального приближения целесообразно сначала построить график соответствующей функции. Для этого можно воспользоваться функциейfplot (f,[-1,3]).

Задаем функцию: >> f=inline("exp(cos(x)*cos(x))-3*sin(0.8*x)+0.5","x").

Строим график: >> fplot(f,[-1,3]).

Вызываем функцию решения уравнения: >> x=fzero(f,0).

Результаты решения приведены на рисунке:

Решение систем линейных уравнений (слау)

Постановка задачи

Требуется найти решение системыn линейных уравнений:

a 11 ·x 1 +a 12 ·x 2 +…+a 1n ·x n =b 1

a 21 ·x 1 +a 22 ·x 2 +…+a 2n ·x n =b 2

a n1 ·x 1 +a n2 ·x 2 +…+a nn ·x n =b n

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

где A – матрица системы, – вектор правых частей, – вектор неизвестных.

При известных A и требуется найти значенияx , при подстановке которых в систему уравнений она превращается в тождество.

Необходимым и достаточным условием существования единственного решения СЛАУ является условие det A≠0 , т.е. определитель матрицыA не равен нулю. В случае равенства нулю определителя матрицаA называетсявырожденной и при этом СЛАУ либо не имеет решения, либо имеет их бесчисленное множество. В дальнейшем будем предполагать наличие единственного решения.

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

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

Задача. Найти корень уравнения с заданной точностью .

В этом случае используется одновременно методы касательных и хорд. Приближение к корню происходит с двух сторон. Рассмотрим четыре случая, которые отвечают возможным комбинациям знаков и .

Из графиков, представленных на рис. 7, метод хорд применяется со стороны вогнутости, а метод касательных – со стороны выпуклости графика.

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

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

Лежащей между точками b0 и искомым корнем , а касательная к дуге в точке А пересекает ось ох в точке а0, лежащей между точками а0 и искомым корнем уравнения (рис. 8).

Полученное значение a1 и b1 дают новое приближение к корню. Приведем расчетные формулы для ai+1и bi+1, выведенные в п.2.1 и 2.2.

Процесс нахождения ai+1 и bi+1 продолжается до тех пор, пока выполняется одно из следующих условий:

, где - Заданная точность;

.

Все округления при вычислениях следует производить в сторону от корня . На рис. 9 представлена блок-схема комбинированного метода хорд и касательных, где n - число итераций; аn, b n− значения приближения корня; F(аn) F(b n) − значения функции в данных точках.

Чтобы применить метод простой итерации для нелинейного уравнения F(x)=0, необходимо преобразовать его к следующему виду:

Это преобразование (приведение уравнения к виду, удобному для итерации) можно выполнить различными способами; некоторые из них будут рассмотрены ниже. Функция называется итерационной функцией.

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

. (3)

Если существует предел построенной последовательности , то, переходя к пределу в равенстве (3) и предполагая функцию непрерывной, получим равенство

Это значит, что – корень уравнения (2).

Метод допускает простую геометрическую интерпретацию. Построим графики функций у = x и у = j(x), (рис. 10,а и 10,б). Корнем x уравнения у = j(x) является абсцисса точки пересечения кривой

у = j(x) с прямой у = x. Взяв в качестве начальной произвольную точку x0 Î , строим ломаную линию. Абсциссы вершин этой ломаной представляют собой последовательные приближения корня x. Из рисунков видно, что если j"(x)<0 на отрезке , то последовательные приближения xn = j(xn-1), колеблются около корня x, если же производная j"(x)>0, то последовательные приближения сходятся к корню монотонно.

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

На рис. 11 рассмотрен пример, когда условие окончания итерационного процесса выполняется на первом шаге итерационного процесса, т. е. , из этого следует, что х0 является приближенным значением искомого корня. Однако из рис. 11 видно, что это неверно, т. к. решением задачи является x.

Для метода итераций следует подбирать функцию j(x) так, чтобы |j"(x)|£ δ <1, в противном случае процесс итерации расходящийся. При этом следует помнить, что скорость сходимости последовательности {xn} к корню x тем выше, чем меньше число δ.

Ключевой момент в применении метода простой итерации – эквивалентное преобразование уравнения F(x)=0 к виду (2). Конечно,

Такое преобразование имеет смысл только тогда, когда оказывается выполненным условие при . Если первая (обычно самая простая и напрашивающаяся) попытка представления уравнения в требуемом виде оказалась неудачной, отчаиваться не следует. В ряде случаев можно использовать специальные приемы. Рассмотрим некоторые из них .

Способ 1 . Если содержит в себе выражение некоторой обратимой на [с; d] функции , причем такой, что на , то следует попытаться заменить уравнение на равносильное с использованием обратной для функции : . Этот способ основан на известном соотношении между производными взаимообратных функций и следствии из него:

То.

Пример. Привести уравнение к виду, пригодному для методом простой итерации на интервале .

Прибавим к правой и левой частям х и получим: . Проверим условие сходимости:

Другой вариант уравнения: . Проверим условие сходимости:

Условие сходимости не выполняется.

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

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

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

Пусть дано уравнение с единственным корнем в . Предположим, что на отрезке [с; d] производная функции F непрерывна, не равна константе и принимает значения одного и того же знака. Будем считать, что , т. к. в противном случае можно рассматривать равносильное уравнение: .

Введем обозначения: .

Ясно, что . Заменим равносильное уравнение уравнением эквивалентным ему

И покажем, что для функции на имеет место условие сходимости.

Для справедливы неравенства: . Разделим их почленно на число М и для разностей между единицей и полученными дробями получим неравенство.

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

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

Если
, то метод хорд дает приближение корня с недостатком, а метод касательных – с избытком:

Если же
, то методом хорд получаем значение корня ч избытком, а методом касательных – с недостатком:

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

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

Если
, то со стороны концаa лежат приближенные значения корня, полученные по методу хорд, а со стороны конца b – значения, полученные по методу касательных, и тогда:
;
.

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

Если же
, то со стороны концаa лежат приближенные значения корня, полученные по методу касательных, а со стороны конца b – значения, полученные по методу хорд, и тогда:
;
.

Комбинированный метод очень удобен при оценке погрешности вычислений. Процесс вычислений прекращается, как только станет выполняться неравенство:
.

За приближенное значение корня следует принять
, где- приближенное значение корняс недостатком,- с избытком.

Пример

Комбинированным методом хорд и касательных уточнить до
корни уравнения.

Решение

Составим таблицу знаков функции:

sign f(x)

Данное уравнение имеет три действительных корня: .

Уменьшим промежутки нахождения корней до длины, равной 1:

sign f(x)

2)уточним комбинированным методом хорд и касательных корень, лежащий в интервале (-7;-6).

Имеем f (-7)=-27<0, f (-6)=37>0 и
,,
. Это означает, что применяем формулы:
;
. Здесьa 0 =-7, b 0 =-6. Вычисления сведем в таблицу:

Из таблицы следует, что

3) Определим
Имеемf (0)=1>0, f (1)=-19<0 и
,,
. Как и в случае нахождения(воспользовавшись теми же формулами, но в которыхa 0 =0, b 0 =1 ), строим таблицу для уточнения искомого корня. В результате получаем
.

4) Для уточнения приближенного корня комбинированным методом хорд и касательных на интервале (3;4) имеем: f (3)=-17<0, f (4)=7>0 и
,,
.

Расчетные формулы в этом случае следующие:
;
. Построив таблицу последовательных вычислений, находим, что
.

Метод итерации (метод последовательных приближений)

Пусть на отрезке отделен вещественный корень непрерывной функции f(x).

Заменим уравнение f(x)=0 эквивалентным ему уравнением x=φ(x).

Выберем каким либо способом x0 є и подставим его в уравнение x=φ(x); тогда имеем x1= φ(x0). Затем это значение x1 подставим снова в правую часть x=φ(x) , то получим х2= φ(x1).

Повторяя этот процесс последовательность, чисел хn= φ(xn-1),которая может сходиться (т.е. х0 , х1 , х2 , ….. , хn , … имеет предел, который и является корнем уравнения f(x)=0) или расходится (в этом случае х0 , х1 , х2 , ….. , хn , … не имеют предела).

Условия, при котором итерационный процесс сходится, формируется в теореме: если уравнение x=φ(x) на отрезке a= φ(x)=b имеет единственный корень и во всех точках этого отрезка производная f "(x) удовлетворяет неравенству | φ" (x)|≤q<1, то итерационный процесс сходится,а нулевое приближение х0 можно взять любое число из отрезка .

Очевидно, что чем меньше | φ" (x)| , тем лучше сходимость итерационного процесса.

Для лучшего уяснения сути метода итерации приведем геометрические итерации a,b,c,d.

Здесь ξ – абцисса точки пересечения функций т.е. искомый корень f(x)=0 ; х0 первое (начальное) приближение корня, x0 є ; x1=φ(x0) (т.к. А0 С0= φ(x0), B1C1 = А0 С0= x1), х2 = φ(x1) , х3 = φ(x2), …. φ(xn-1)=xn.

Последовательное приближение х0 , х1 , х2 , ….. , хn , … (общие абциссы точек графиков обеих функций) монотонно убывают, что характеризует сходящийся итерационный процесс (каждая последующая приближение хn ближе к истинному корню ξ чем каждое предыдущее xn-1). Отметим, что в рассматриваемом случае 0< φ" (x)<1 , кривая φ(x) пересекает биссектрису у=х в точке М=(ε, φ(ε)) и при х>ξ кривая у= f(x) лежит под биссектрисой

Здесь φ" (x)<0 , но по абсолютной величине меньше 1 , т.е. | φ" (x)|<1.

Итерационный процесс и в этом случае сходится, однако приближения колеблются около точного значения корня ξ. В отличие от случая «а», где ломанная линия А0 , B1 , A1 , B2 ,A2……… имеет вид лестницы, ломаная линия А0 , B1 , A1 , B2 ,A2……… случая «б» имеет вид спирали.

Здесь | φ" (x)|>1 , кривая у= φ(x) пересекает биссектрису у=х в точке М=(ξ, φ(ξ)) и при х>ξ лежит над биссектрисой.В таком случае итерационный процесс расходится.

Здесь | φ" (x)|>1.Последовательные приближения удаляются от точного значения корня ξ т.е. итерационный проце сс расходится.

Итак, если в некоторой окрестности корня ξ уравнение х=φ(x) производная φ" (x) сохраняет постоянный знак выполняется неравенство

| φ" (x)|≤q<1, причем φ" (x)>0, то последовательностные приближения

φ(xn-1)=xn (n є N , x0 є ) сходятся к корню монотонно. В том же случае, если φ" (x)<0 , то последовательные приближения колеблются около точного значения корня ξ.

Проверкой точности является следующее соотношение

|ξ- xn |≤(q/(1-q))| xn – xn-1 |, где «q» определяется из выражения | φ" (x)|≤q<1.

Если ставится условие, что истинное значение корня ξ должно отличатся от приближенного значения на величину Δ , то |ξ- xn |≤Δ и | xn – xn-1 |≤Δ((1-q)/q)

Пример

Методом итераций уточнить до 10^(-4) корень уравнения 5х³ - 20х² +3=0 , заключенный на отрезке .

Решение

Данное уравнение следует привести к виду х= φ(x) .Это можно сделать по разному, например:

х=х+(5х²-20х+3), где φ1(x)=5х²-19х+3;

х=((20х-3)/20)^(1/3) , где φ2(x) =((20х-3)/20)^(1/3);

х=((5х³+3)/20) , где φ3(x)=((5х³+3)/20)

Поскольку условие достаточности | φ" (x)|≤q<1 характеризует сходимость итерационного процесса,то определим φj(x) для вычисления последовательных приближений:

| φ"1 (x)|=|15x²-19|>1 на ;

| φ"2 (x)|=|(1/3)*(((25)^(1/3) *4) / ((20x-3)^(2)) ^(1/3))|>0 на ;

| φ"3 (x)|=|((15х²)/20)|=(3/4)x²<1 на ;

Следовательно, можно воспользоваться функцией φ3(x) для?????? приближенного корня по формуле:

Xn = (5х³n-1 +3)/20

За начальное приближение возьмем max φ"(x) на , т.е. х0=0,75=q

Пользуясь формулой | xn – xn-1 |≤(ε*(1-q))/q,

Определим какой должна быть разность | xn – xn-1 | ,что бы была достигнута заданная конечность, т.е.

| xn – xn-1 |≤(0,0001(1-0,75))/0.75=0.00003

Таким образом когда обсолютная величина разности | xn – xn-1 | не превзойдет 0,00003 , итерационный процесс следует прекратить и считать заданную точность достигнутой.

Вычисления сведем в таблицу:

Из этой таблицы

х4 – x5=0,1541413-0,151361=0,0000 , т.е.

Пример

Найти методом итераций наименьший положительный корень(с пятью значащими цифрами) уравнения!

Cos(x) –(1/x)sin(x)=0.

Заменяем исходное уравнение эквивалентным ему: х=tg(x) и построив график функции y1=x; y2=tg(x), находим что х0=(3π)/2=4.7.

Однако к уравнению х=tg(x) непосредственно метод итераций применить нельзя, т.к. при любом значении х φ" (x)=(tg(x))"=(1/cos²(x)) больше единице (т.е. не соблюдается достаточное условие сходимости итерационного процесса | φ" (x)<1|).

Поэтому перейдем к обратным функциям, т.е. к уравнению

φ" (x)=(arctg(x))"=(1/(1+x²))<1 при x≠0

Уравнением x= arctg(x), эквивалентное исходному уравнению

Cos(x) –(1/x)sin(x)=0, решаем при помощи формулы

Xn =arctg(xn-1) , где х0=4,7

Итерационный процесс заканчиваем тогда, когда с необходимой точностью совпадут значения xn и xn-1

Выполнив вычисления приведенные в таблице

Получаем х=4,4934

Пример

Вычислит с точностью до ε=10^(-5) корень уравнения (е^(x))-x²=0

Решение

Перепишем заданное уравнение в виде (е^(x))=x²

И отделим корни графически

Единственный корень уравнения (е^(x))-x² лежит в интервале [-0.8;-0.7]

Действительно:

f(-0,8)= (е^(-0,8))-0,8²=0,44933-0,64=-0,19607<0 ,

f(-0,7)= (е^(-0,7))-0,7²=0,49659-0,49=0,00659>0 ,

т.е. f(-0.8)*f(-0.7)<0.

Методом проб сузим интервал. В котором находится корень ξ .

Имеем: [-0.725;-0.7].

Из уравнения(е^(x))-x²=0 получаем х=-((е^х)^(1/2)) (пер знаком радикала стоит знак минус, т.к. известно, что корень ξ отрицателен).

Проверим каким является итерационный процесс для функции

φ(x)= -(х/(e^2))

φ"(x)=-(1/2)e^(x/2); | φ"(-0.725)|=0.34727;

|φ" (-0.7)|=0.35230,

Поскольку |φ" (x)|<1 ,на [-0.725;-0.7] , то итерационный процесс сходится, т.е. удовлетворяется требование |φ"(x)|≤q<1.

Возьмем q=0.36 ,а т.к.ε=10^(-5), то из(q/(1-q)) | xn – xn-1| ≤ε получаем

| xn – xn-1|≤ ε((1-q)/q) и | xn – xn-1|≤10^(-5)(1-0.36)/(0.36)=18*10^(-5)

Таким образом, требуемая точность будет достигнута, если выполняется неравенство | xn – xn-1| ≤ 0.00002 .

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

[-0.725;-0.7]. Примем х0=-0,7.

Вычисления сведем в таблицу

Т.к. | x6 – x5|=|-0.70346+0.70348|=0.00002 , то ξ≈-0,70346

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

Решение матричных уравнений.

Матричное уравнение

, где А - собственная матрица, Х – вектор-столбец неизвестных, В – вектор-столбец свободных членов системы:

А=
, Х=, В=, решается умножением обеих его частей на обратную матрицу
:

Поскольку
(где Е – единичная матрица), то
. Отсюда
.

Союзная матрица по отношению к данной матрице А есть транспонированная матрица алгебраическихвсех элементов матрицы А:

Пример: Используя матричную запись, решить систему линейных уравнений:

Решение: Имеем
, т.е.:

Находим
:
;

. Поскольку
, то
. Отсюда

Замечание:

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

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

Искомые элементы треугольных матриц
находят следующим образом:

Пример:

Для матрицы
найти обратную, разложив данную матрицу на произведение двух треугольных.

Решение:

Вычисляем:

Т.е. А можно представить как
, т.е.:

или

Составляем уравнения:

Решая эти уравнения, находим:

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

. Для нахождения обратной матрицы
найдем
. Пусть
=
, тогда
, или

Составляем уравнения:
, отсюда находим:
. Следовательно:
. Найдем
, учитывая, что
:

Отсюда находим элементы обратной матрицы
:

. Обратная матрица
:

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

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

Пример:

Решить по формулам Крамера систему линейных уравнений:

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

Теперь по формулам Крамера получаем решение системы:

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

Решение системы уравнений методом Гаусса (методом последовательного исключения неизвестных)

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

Процесс решения системы уравнений методом Гаусса состоит из прямого и обратного хода.

Прямой ход – преобразование заданной системы уравнений к эквивалентной системе с верхней треугольной матрицей.

Обратный ход – получение решения системы.

Пример .

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

Преобразованная система уравнений имеет вид:

Обратный ход:

а) схема единственного деления.

Операции прямого и обратного хода удобно вести по вычислительной схеме единственного деления. Как для системы 3-х уравнений с 3-мя неизвестными имеем вычислительную схему:

	№ строки	Коэффициенты при			Свобоныые члены	Контроль
						Контрольные суммы	Строчные суммы
Прямой ход
Обратный ход

В этой схеме:
- ведущий элемент;;
- ведущий элемент;;
;
- контрольные суммы, над которыми выполняются те же действия, что и над остальными элементами строки.

Пример .

По схеме единственного деления решение этой системы уравнений проводиться в следующей последовательности:

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

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

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

Так,
.

Строчная сумма четвертой строки равна 1-0,1667+0,2500-0,5000=0,5833, а контрольная сумма (1,20-0,20+0,30-0,60)*0,8333=0,70*0,8333=0,5833. Совпадение строчной и контрольной сумм означает отсутствие вычислительных ошибок.

3) вычислив коэффициенты

вычислительной системы

, где
. Заполним строки 5 и 6 схемы единственного деления. Очевидно:

4) повторяем процесс, т.е. строки 7 и 9 заполняем по тому же правилу, что и строки 4 и 8 – по правилу заполнения строк 5 и 6. Текущий контроль вычислений осуществляется вычислением контрольных сумм и сравнением их со строчными для каждой строки

	№ строки	Коэффициенты при			Свободные члены	Контроль
						Контрольные суммы	Строчные суммы
Прямой ход
Обратный ход

5) числа, заполняющие 4, 7 и 9 строки схемы, представляют собой коэффициенты и свободные члены простейшей системы трех уравнений:
эквивалентной данной. Решение этой системы осуществляется по формулам обратного хода:

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

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

и учитываем, что
)

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

Б) Схема с выбором главного элемента. Эту схему вычислений, лучшей по точности из всех вычислительных схем по методу Гаусса, проиллюстрируем на этом же примере. Первые три строки схемы, за исключением третьего столбца, заполняются аналогично схеме единственного деления:

	№ строки		Коэффициенты при			Свободные члены	Контроль
							Контрольные суммы	Строчные суммы
Прямой ход

Выбираем в таблице наибольший по модулю коэффициент (который будем называть главным элементом). Имеем=1,60 (в таблице выделен цветом). В третьем столбце выписываются взятые с обратным знаком частные от деления на главный элементвсех элементов столбца, содержащего главный элемент (в данном случае пятого столбца). Прибавляя теперь к каждой из строк схемы (столбцы 4-8) строку с главным элементом, умноженную предварительно на соответствующий множитель и третьего столбца, получим:

Прямой ход

Здесь контроль производиться так же, как и в схеме единственного деления.

Выполненные действия привели к исключению из исходной системы неизвестной . В оставшейся системе (строки 4 и 5) выбираем новый главный элемент (это коэффициент при, т.е. 1,494).

Все последующие действия выполняются аналогично предыдущим, т.е. получаем:

Прямой ход

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

Обратный ход:

Полностью схема с выбором главного элемента для нашего примера имеет вид:

	№ строки		Коэффициенты при			Свободные члены	Контроль
							Контрольные суммы	Строчные суммы
Прямой ход

Округляя запасной знак, окончательно получаем: =-0,44;=-0,12;=-0,17.

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

В отличие от прямых (точных) методов, итерационные методы являются бесконечно повторяющимися процессами. Если этот процесс сходящийся, то на каждом последующем шаге получается более точное приближение к искомому решению данной системы уравнений.

а) Метод простой итерации.

Для итерационных методов систему линейных уравнений
приводят к виду

. В качестве начального приближения
целесообразно взять свободные членысистемы, а дальнейшиеk- ые приближения строить по формулам:

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

Действительно, так как .

б) Достаточный признак сходимости итерационного процесса.

Если максимальная сумма модулей коэффициентов при неизвестных
каждого уравнения системы меньше единицы, т.е.
то процесс итерации сходится.

Пример: Исследовать систему уравнений на сходимость итерационного процесса.

Имеем:

Проверка:
, то итерационный процесс для заданной системы трех уравнений сходиться.

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

Рассмотрим пример решения систем уравнений методом итерации:

предполагая, что абсолютные погрешности коэффициентов и свободных членов системы не превышают 0,00005.

Для заданной системы уравнений удовлетворяется условие достаточности сходимости итерационного процесса.

Примем за начальные приближения решения
свободные члены системы:

Последующие вычисления приближений выполняем по формулам:

Результат вычислений сведем в таблицу:

Приближенно	Коэффициенты при			Свободные члены

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

г) О приведении линейной системы к виду, пригодному к методу итерации.

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

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

В том случае, если диагональные элементы матрицы А отлична от нуля, т.е.

, и

: то систему
можно записать в виде:

,

а элементы матрицы С будут:

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

.

Пример.

Привести к виду, пригодному для метода итерации, систему:

В этой системе
,
. Имеем:

Для полученной системы выполняются условия сходимости:

Пример . Система:

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

Условия сходимости для полученной системы выполняются, т.к.:

д) Метод Зейделя .

Итерационный метод Зейделя решения линейных систем уравнений представляет собой видоизменение метода простой итерации.

В этом методе линейная система задается в виде
, а приближения строятся по формулам:

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

Пример . Методом Зейделя решить систему:

Поскольку достаточные условия сходимости итерации процесса выполнены, т.е.: 0,1667+0,2500<1; 0,1250+0,0625<1; 0,2000+0,0667<1, то имеем решение системы.

Последовательные приближения для k=0; k=1:

Результаты вычислений сведем в таблицу:

Приближенно	Коэффициенты при			Свободные члены

Таким образом:

Численное интегрирование.

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

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

а) Метод прямоугольников.

Этот метод основании на непосредственном определении интеграла:
где
интегральная сумма, соответствующая некоторому разбиению отрезка
и некоторому выбору точек
на отрезках разбиения.

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

-шаг,
;

-шаг,
.

Очевидность этих формул следует из графической интерпретации приближенной площади криволинейной трапеции: ступенчатыми фигурами.

Пример. С помощью формул левых и правых прямоугольников вычислить , пологая
.

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

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

Имеем,
.

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

б) Метод трапеций.

В этом случае интегральная сумма

есть среднее арифметическое

формул правых и левых прямоугольников:

.

(*)Легко усмотреть геометрический смысл этой формулы, в которой подинтегральная функция заменена кусочно-линейной (говорят в этом случае о линейной интерполяции дискретной функции. Это означает, что площадь криволинейной трапеции
заменяется суммой площадей трапеций
.

Приведя в формуле (*) подобные члены, окончательно получаем:

Эту формулу принято называть общей формулой трапеций.

Пример. Пользуясь общей формулой трапеций вычислить

при
.

Решение. Здесь .

на участке

Имеем:
, где
- уравнение параболы.

Коэффициенты

.

в виде:.

Положим
, имеем:

(здесь
).

Аналогично:

Отсюда:
.

Площадь под параболой есть

Или, учитывая, что

Окончательно:

.

в) Метод Симпсона (метод парабол).

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

Имеем:
, где
- уравнение параболы.

Коэффициенты
определяются из условия прохождения параболы через точки

Однако это приводит к довольно длинным выкладкам:
.

Поступим иначе. Запишем искомую параболу на отрезке
в виде:.

Положим
, имеем:

(здесь
).

Аналогично:

Отсюда:
.

Площадь под параболой есть

Или, учитывая, что

Окончательно:

.

Для интеграла по всему промежутку
получаем:

Эта формула называется формулой Симпсона.

Пример. Найти по формуле Симпсона при.

Решение. Значения
в точках отрезка:.

Формула Симпсона дает .

Т.к.
, то ошибка

(или
).

В то же время ошибка общей формулы трапеций значительно выше:

(или
).

Пример. Найти
.

Решение. Пусть .

По формуле трапеции, получаем:

.

По формуле Симпсона, получаем:

.

Точное значение
,

а соответствующие погрешности равны
и
(или
и
).

Дифференцирование функций, заданных приближенно.

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

.

Аналогично,

Пример. Вычислить значения
и
, если

Решение. Результаты вычислений
и
сведем в таблицу:

Численное интегрирование дифференциальных уравнений.

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

и
.

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

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

а) Метод Эйлера.

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

(Действительно, ).

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

Геометрически интегральная кривая
заменяется ломанной (называемой ломаной Эйлера).

Рабочая формула для определения значений
по методу Эйлера имеет вид:

, где
,
,
.

Пример.

с начальным условием
, выбрав шаг
.

Решение. Результаты вычислений сведем в таблицу:

						Точное решение

Из таблицы следует, что абсолютная погрешность
, а относительная погрешность
.

Решение системы дифференциальных уравнений и дифференциальных уравнений высших порядков методом Эйлера требует их преобразования к системам уравнений 1-го порядка.

Так, для системы

с начальными условиями
и
приближенные значения
и
вычисляются по формулам:

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

Решение. С помощью подстановок
из заданного уравнения получаем:

с начальными условиями .

В полученной системе:

.

Вычисления сведем в таблицу:

В этой таблице первая строка заполняется так: для того,

что
;
;
;
,

.

Используя формулы ,,

получаем

;
;

;
.

Таком образом, во второй строке таблицы записываем

;
;
;
. По этим значениям находим:

,

и, следовательно,

Заполнение таблицы при
производится аналогично.

б) Метод Ронге-Кутта.

Этот метод, имеющий много общего с методом Эйлера, является методом повышенной точности.

Пусть на отрезке
требуется найти численное решение уравнения
с начальными условиями
.

В методе Рунге-Кутта, так как и в методе Эйлера, последовательные значения искомой функции
определяются по формуле
.

Представим приращение функции
членами довключительно ряда Тейлора разложения функции:

Где
,

,
,
,
,
- производные, определяемые последовательным дифференцированием уравнения
.

Вместо непосредственных вычислений приращения
по полученной формуле в методе Рунге-Кутта определяются четыре числа
;
;
;таких, что:
.Таким образом, для каждой пары
находят
и затем
.

Вычисления по методу Рунге-Кутта удобно вести по схеме:

В столбце 2 и 3 текущей строки записывается нужное значение и, а результаты подставляются в правую часть уравнения
, записывается в четвертый столбец той же строки. В пятом столбце таблицы получены значения столбцаумножаются на шаг интегрирования. Результаты шестого столбца суммируются и делятся на 6, т.е. определяется
и
.

Метод Ньютона называют также методом касательных. Комбинируя метод хорд и метод Ньютона, можно построить метод отыскания вещественных корней уравнения f(x) = 0, в котором при прежних предположениях относительно f(x) на каждом шаге итерационного процесса мы получаем два приближения к корню и , причем где с –точное значение корня.

1. Условия на применение метода те же, что и в методе Ньютона.

Пусть известен отрезок , который содержит один корень уравнения: f(x) = 0. Функция f(x) является дважды непрерывно дифференцируемой на (f(x) Î C 2 ). Функция f принимает на концах отрезка значения разных знаков (f(a)×f(b) < 0). Первая и вторая производные функции f не обращаются в ноль на отрезке

(f ¢ ¹ 0, f ¢¢ ¹ 0).

2. Возможны два случая:

· если f(a)×f ¢¢ (x) > 0, то слева применяем метод Ньютона, а справа метод хорд.

Формулы метода:

· если f (b )×f ¢¢ (x ) > 0, то слева применяем метод хорд, а справа метод Ньютона (метод касательных).

Формулы метода:

В качестве точек начального приближения выбираются: x 0 = a, .

4. Условие остановки итерационного процесса: , при выполнении этого условия любая точка из отрезка приближает корень уравнения с точностью e.

Чаще всего принимают: .

На рис. 2.8. иллюстрируется применение комбинированного ме­тода хорд и касательных. В рас­сматриваемом случае справа при­меняется метод Ньютона, а слева – метод хорд.

Рис. 2.8. Геометрический смысл комбинированного метода хорд и касательных

Построить алгоритм для уточнения корня уравнения x 3 + 3x – 1 = 0 комбинированным методом хорд и касательных с точностью e на отрезке .

1. В предыдущих примерах мы проверили, что отрезок содержит один корень уравнения, и выполняются все условия для применения метода Ньютона:

2. Определим, какой из методов нужно применять слева, а какой справа.

Каждый уважающий себя инженер или IT-шник должен быть на «ты» с вычислительной математикой и ее численными методами для решений различных задач, возможно даже тривиальных, которые «голову в порядок приводят». В процессе изучения хотелось обратить более тщательное внимание на методы приближенного решения алгебраических и трансцендентных уравнений, а так же их анализ.

Методы численного решения нелинейных уравнений

Задачу решения я разделил на 3 части:

• Аналитический способ отделения корней
• Численные методы уточнения корней
• Программная реализация вычислительного процесса

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

Метод дихотомии или половинного деления.

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

Комбинированный метод или метод хорд и касательных

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

Метод итераций

Предварительно необходимо преобразовать уравнение f(x) = 0 к виду x = φ(x).
В качестве начального приближения x0 выбирается любая точка интервала .
Выделяют 2 итерационных метода: лестница и спираль. Если знак производной φ(x) положителен, то используют метод лестницы и наоборот спирали.

Главным и достаточным условием сходимости итерационного процесса является |φ"(x)|<1.
Достоинство метода. Надежность (обладает самокоррекцией): ошибка в вычислениях, при которой х остается в пределах , не влияет на конечный результат, т.к. ошибочное значение можно рассматривать как новое х0.

Практика. Применение методов.

Возьмем для примера задачу из области автоматизированного управления - нахождения нулей характеристического уравнения передаточной функции замкнутой системы автоматического управления высокого порядка для оценки ее устойчивости по методу Ляпунова. Сам метод выходит за рамки данного поста, но в прямом методе Ляпунова используется нахождение нулевых корней для выявления устойчивости системы. А для нахождения корней вполне подходят перечисленные методы. Какой метод эффективнее? На этот вопрос сложно ответить не зная конкретной системы к которой это будет применяться. Следует учитывать не только скорость операций, но так же и занимаемые ресурсы.

Вывод:

1. Рассмотренные методы уточнения корней одинаково применимы как к алгебраическим, так и к трансцендентным уравнениям.
2. Операция отделения корней значительно сложнее для трансцендентных уравнений, чем для алгебраических.
3. Наиболее производительным из рассмотренных является комбинированный метод.

Мат.часть описанных методов.

PS: Первый пост и еще не совсем освоился. Помещаю пост в алгоритмы, т.к. блога по выч.мату не нашел.