Математика как наука возникла в связи с необходимостью решения практических задач: измерений на местности, навигации и т.д. Вследствие этого математика была численной математикой и ее целью было получение решения в виде числа. Численное решение прикладных задач всегда интересовало математиков. Крупнейшие представители прошлого сочетали в своих исследованиях изучение явлений природы, получение их математического описания, т.е. его математической модели и его исследование. Анализ усложненных моделей потребовал создания специальных, обычно численных методов решения задач. Названия некоторых таких методов свидетельствуют о том, что их разработкой занимались крупнейшие ученые своего времени. Это методы Ньютона, Эйлера, Лобачевского, Гаусса, Чебышева, Эрмита.
Настоящее время характерно резким расширением приложений математики, во многом связанным с созданием и развитием средств вычислительной техники. В результате появления ЭВМ менее чем за 40 лет скорость выполнения операций возросла от 0,1 операции в секунду при ручном счете до 10 операций в секунду на современных ЭВМ.
Распространенное мнение о всемогуществе современных ЭВМ порождает впечатление, что математики избавились от всех хлопот, связанных с численным решением задач, и разработка новых методов для их решения уже не столь существенна. В действительности дело обстоит иначе, поскольку потребности эволюции ставят, как правило, перед наукой задачи, находящиеся на грани ее возможностей. Расширение возможностей приложения математики обусловило математизацию различных разделов науки: химии, экономики, биологии, геологии, географии, психологии, медицины, техники и др.
Можно выделить два обстоятельства, которые первоначально обусловили стремление к математизации наук:
во-первых, только применение математических методов позволяет придать количественный характер исследованию того или иного явления материального мира;
во-вторых, и это главное, только математический способ мышления делает объекта. Такой метод исследования называют вычислительным экспериментом исследование в полной мере объективным.
В последнее время появился еще фактор, оказывающий сильное воздействие на процессы математизации знаний. Это быстрое развитие средств вычислительной техники. Применение ЭВМ для решения научных, инженерных и вообще прикладных задач целиком базируется на их математизации.
Математические модели.
Современная технология исследования сложных проблем основана на построении и анализе, обычно с помощью ЭВМ, математических моделей изучаемого. Обычно вычислительный эксперимент, как мы уже видели, состоит из ряда этапов: постановка задачи, построение математической модели (математическая формулировка задачи), разработка численного метода разработка алгоритма реализации численного метода, разработка программы, отладка программы, проведение расчетов, анализ результатов.
Итак, применение ЭВМ для решения любой научной или инженерной задачи неизбежно связано с переходом от реального процесса или явления к его математической модели. Таким образом, применение моделей в научных исследованиях и инженерной практике есть искусство математического моделирования.
Моделью обычно называют представляемую или материально реализуемую систему, воспроизводящую основные наиболее существенные черты данного явления.
Основные требования, предъявляемые к математической модели - адекватность рассматриваемому явлению, т.е. оно должно достаточно отражать характерные черты явления. Вместе с тем она должна обладать сравнительной простотой и доступностью исследования.
Математическая модель отражает зависимость между условиями протекания изучаемого явления и его результатами в тех или иных математических конструкциях. Чаще всего в качестве таких конструкций используются следующие математические понятия: функция, функционал, оператор, числовое уравнение, обыкновенное дифференциальное уравнение, дифференциальное уравнение в частных производных.
Математические модели можно классифицировать по разным признакам: статические и динамические, сосредоточенные и распределенные; детерминированные и вероятностные.
Рассмотрим задачу нахождения корней нелинейного уравнения
Корнями уравнения (1) называются такие значения х, которые при подстановке обращают его в тождество. Только для простейших уравнений удается найти решение в виде формул, т.е. аналитическом виде. Чаще приходится решать уравнения приближенными методами, наибольшее распространение среди которых, в связи с появлением компьютеров, получили численные методы.
Алгоритм нахождения корней приближенными методами можно разбить на два этапа. На первом изучается расположение корней и проводится их разделение. Находится область , в которой существует корень уравнения или начальное приближение к корню x 0 . Простейший способ решения этой задачи является исследование графика функции f(x) . В общем же случае для её решения необходимо привлекать все средства математического анализа.
Существование на найденном отрезке , по крайней мере, одного корня уравнения (1) следует из условия Больцано:
f(a)*f(b)<0 (2)
При этом подразумевается, что функция f(x) непрерывна на данном отрезке. Однако данное условие не отвечает на вопрос о количестве корней уравнения на заданном отрезке . Если же требование непрерывности функции дополнить ещё требованием её монотонности, а это следует из знакопостоянства первой производной, то можно утверждать о существовании единственного корня на заданном отрезке.
При локализации корней важно так же знание основных свойств данного типа уравнения. К примеру, напомним, некоторые свойства алгебраических уравнений:
где вещественные коэффициенты.
- а) Уравнение степени n имеет n корней, среди которых могут быть как вещественные, так и комплексные. Комплексные корни образуют комплексно-сопряженные пары и, следовательно, уравнение имеет четное число таких корней. При нечетном значении n имеется, по меньшей мере, один вещественный корень.
- б) Число положительных вещественных корней меньше или равно числа переменных знаков в последовательности коэффициентов. Замена х на -х в уравнении (3) позволяет таким же способом оценить число отрицательных корней.
На втором этапе решения уравнения (1), используя полученное начальное приближение, строится итерационный процесс, позволяющий уточнять значение корня с некоторой, наперед заданной точностью. Итерационный процесс состоит в последовательном уточнении начального приближения. Каждый такой шаг называется итерацией. В результате процесса итерации находится последовательность приближенных значений корней уравнения. Если эта последовательность с ростом n приближается к истинному значению корня x , то итерационный процесс сходится. Говорят, что итерационный процесс сходится, по меньшей мере, с порядком m, если выполнено условие:
где С>0 некоторая константа. Если m=1 , то говорят о сходимости первого порядка; m=2 - о квадратичной, m=3 - о кубической сходимостях.
Итерационные циклы заканчиваются, если при заданной допустимой погрешности выполняются критерии по абсолютным или относительным отклонениям:
или малости невязки:
Эта работа посвящена изучению алгоритма решения нелинейных уравнений с помощью метода Ньютона.
Существует много различных методов решения нелинейных уравнений, некоторые из них представлены ниже:
- 1)Метод итераций . При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x). Задаются начальное значение аргумента x 0 и точность е. Первое приближение решения x 1 находим из выражения x 1 =f(x 0), второе - x 2 =f(x 1) и т.д. В общем случае i+1 приближение найдем по формуле xi+1 =f(xi). Указанную процедуру повторяем пока |f(xi)|>е. Условие сходимости метода итераций |f"(x)|
- 2)Метод Ньютона . При решении нелинейного уравнения методом Ньтона задаются начальное значение аргумента x 0 и точность е. Затем в точке(x 0 ,F(x 0)) проводим касательную к графику F(x) и определяем точку пересечения касательной с осью абсцисс x 1 . В точке (x 1 ,F(x 1)) снова строим касательную, находим следующее приближение искомого решения x 2 и т.д. Указанную процедуру повторяем пока |F(xi)| > е. Для определения точки пересечения (i+1) касательной с осью абсцисс воспользуемся следующей формулой
x i+1 =x i -F(x i) F"(x i).
Условие сходимости метода касательных F(x 0) F""(x)>0, и др.
3). Метод дихотомии. Методика решения сводится к постепенному делению начального интервала неопределённости пополам по формуле
С к =а к +в к /2.
Для того чтобы выбрать из двух получившихся отрезков необходимый, надо находить значение функции на концах получившихся отрезков и рассматривать тот на котором функция будет менять свой знак, то есть должно выполняться условие f (а к)* f (в к)<0.
Процесс деления отрезка проводится до тех пор, пока длина текущего интервала неопределённости не будет меньше заданной точности, то есть в к - а к < E. Тогда в качестве приближенного решения уравнения будет точка, соответствующая середине интервала неопределённости.
4). Метод хорд . Идея метода состоит в том, что на отрезке строится хорда стягивающая концы дуги графика функции y=f(x), а точка c, пересечения хорды с осью абсцисс, считается приближенным значением корня
c = a - (f(a)Ч (a-b)) / (f(a) - f(b)),
c = b - (f(b)Ч (a-b)) / (f(a) - f(b)).
Следующее приближение ищется на интервале или в зависимости от знаков значений функции в точках a,b,c
x* О , если f(с)Ч f(а) > 0 ;
x* О , если f(c)Ч f(b) < 0 .
Если f"(x) не меняет знак на , то обозначая c=x 1 и считая начальным приближением a или b получим итерационные формулы метода хорд с закрепленной правой или левой точкой.
x 0 =a, x i+1 = x i - f(x i)(b-x i) / (f(b)-f(x i), при f "(x)Ч f "(x) > 0 ;
x 0 =b, x i+1 = x i - f(x i)(x i -a) / (f(x i)-f(a), при f "(x)Ч f "(x) < 0 .
Сходимость метода хорд линейная
Алгебраические и трансцендентные уравнения. Методы локализации корней.
Наиболее общий вид нелинейного уравнения:
f(x) =0 (2.1)
где функция f(x) определена и непрерывна на конечном или бесконечном интервале [а, b].
Определение 2.1. Всякое число, обращающее функцию f(x) в нуль, называется корнем уравнения (2.1).
Определение 2.2. Число, называется корнем k-ой кратности, если при вместе с функцией f(x) равны нулю ее производные до (к-1)-го порядка включительно:
Определение 2.3. Однократный корень называется простым.
Нелинейные уравнения с одной переменной подразделяются на алгебраические и трансцендентные.
Определение 2.4 . Уравнение (2.1) называется алгебраическим, если функция F(x) является алгебраической.
Путем алгебраических преобразований из всякого алгебраического уравнения можно получить уравнение в канонической форме:
где -- действительные коэффициенты уравнения, х -- неизвестное.
Из алгебры известно, что всякое алгебраическое уравнение имеет, по крайней мере, один вещественный или два комплексно сопряженных корня.
Определение 2.5. Уравнение (2.1) называется трансцендентным, если функция F(x) не является алгебраической.
Решить уравнение (2.1) означает:
- 1. Установить имеет ли уравнение корни.
- 2. Определить число корней уравнения.
- 3. Найти значения корней уравнения с заданной точностью.
Встречающиеся на практике уравнения часто не удается решить аналитическими методами. Для решения таких уравнений используются численные методы.
Алгоритм нахождения корня уравнения с помощью численного метода состоит из двух этапов:
- 1) отделение или локализация корня, т.е. установление промежутка , в котором содержится один корень:
- 2) уточнение значения корня методом последовательных приближений.
Методы локализации корней. Теоретической основой алгоритма отделения корней служит теорема Коши о промежуточных значениях непрерывной функции.
Теорема 2.1. Если функция у = f(х) непрерывна на отрезке [а,b] и f(а)=А, f(b)=В, то для любой точки С, лежащей между А и В, существует точка, что.
Следствие. Если функция у = f(х) непрерывна на отрезке [а,b ] и на его концах принимает значения разных знаков, то на этом отрезке существует хотя бы один корень уравнения f(х) = 0.
Пусть область определения и непрерывности функции является конечным отрезком [а,b] . Разделим отрезок на n частей: ,
Вычисляя последовательно значения функции в точках находим такие отрезки, для которых выполняется условие:
т.е. , или, . Эти отрезки и содержит хотя бы по одному корню.
Теорема 2.2. Если функция у = f(х) непрерывна на отрезке [а;b ], f(а)f(b)<0 и f`(х) на интервале (а;b) сохраняет знак, то внутри отрезка [а;b] существует единственный корень уравнения f(х) = 0.
Для отделения корней можно использовать также график функции у = f(х). Корнями уравнения (2.1) являются те значения х, при которых график функции y=f(х) пересекает ось абсцисс. Построение графика функции даже с малой точностью обычно дает представление о расположении корней уравнения (2.1). Если построение графика функции у=f(x) вызывает затруднение, то исходное уравнение (2.1) следует преобразовать к виду ц1(х) = ц2(х) таким образом, чтобы графики функций у = ц1(х) и у = ц2(х) были достаточно просты. Абсциссы точек пересечения этих графиков и будут корнями уравнения (2.1).
Пример 1. Отделить корни уравнения x 2 -2cosx=0.
Решение. Рассмотрим два способа отделения корней.
- а) Графический способ. Перепишем уравнение в виде x 2 =2cosx и построим график функций y=x 2 и y=2cosx в одной и той же системе координат (рисунок 5). так как эти графики пересекаются в двух точках, уравнение имеет два корня, расположенные симметрично относительно начала координат на интервалах (-/2; 0) и (0; /2).
- б) Аналитический способ. Пусть f(x)= x 2 -2cosx. Так как f(x) четная функция, то достаточно рассмотреть только неотрицательные значения x. В силу неравенства 2cosx2
Производная f"(x) =2(x+sinx). На интервале (0; /2) f"(x) >0 , следовательно, f(x) здесь монотонно возрастает и ее график может пересечь ось х не более, чем в одной точке. Заметим, что f(0)=- 2<0, а f(/2)=(/2) 2 >0. Значит, уравнение имеет один положительный корень, лежащий на интервале (0; /2). В силу четности функции уравнение имеет также один отрицательный корень, симметричный положительному. Теперь перейдем к уточнению корня. Для применения комбинированного метода уточнения корня необходимо убедится, что f ""(x) на (0; /2) сохраняет знак, и выбрать начальное приближение корня для применения метода касательных. Оно должно удовлетворять условию: f(x)f ""(x) >0. Так как f ""(x) =2(1+cosx) положительна на , то за начальное приближение корня в методе касательных может быть взято /2. Следовательно, можно положить x =/21,570796, x 1 =0 (см схему алгоритма). В нашем случае метод хорд будет давать приближенное значение корня с недостатком, а метод касательных - с избытком.
Рассмотрим один итерационный шаг уточнения корня. Вычислим значения f(0), f(/2), f"(/2). Новые значения x 1 и x найдем соответственно по формулам:
|x-x 1 |=0,387680,4>10 -4 =.
Заданная точность не достигнута, и вычисления нужно продолжить.
|
Номер итерации |
x 1 |
f(x 1 ) |
|x- x 1 | |
|||
Следовательно, приближенное значение корня с нужной точностью найдено в результате трех итераций и приближенно равно 1,0217.
В силу симметрии графика функции f(x) значение второго корня приближенно равно -1,0217.
Уточнение корня.
Постановка задачи . Допустим, что искомый корень уравнения (2.1) отделен, т.е. найден отрезок [а; b], на котором имеется один и только один корень уравнения. Любую точку этого отрезка можно принять за приближенное значение корня. Погрешность такого приближения не превосходит длины [а; b]. Следовательно, задача отыскания приближенного значения корня с заданной точностью сводится к нахождению отрезка [а; b] (b- a <), содержащего только один корень уравнения (2.1). Эту задачу обычно называют задачей уточнения корня.
Описание численных методов. Численные методы позволяют найти решения определенных задач, заранее зная, что полученные результаты будут вычислены с определенной погрешностью, поэтому для многих численных методов необходимо заранее знать «уровень точности», которому будет соответствовать полученное решение.
В этой связи задача нахождения корней многочлена вида (3.1)
представляет особый интерес, т.к. формулы нахождения корней даже кубического уравнения достаточно сложны. Если необходимо отыскать корни многочлена, степень которого равна, например, 5 - то без помощи численных методов не обойтись, тем более, что вероятность наличия у такого многочлена натуральных (или целых, или точных корней с «короткой» дробной частью) довольно мала, а формул для нахождения корней уравнения степени, превышающей 4, не существует. Де-факто все дальнейшие операции будут сводиться лишь к уточнению корней , интервалы которых приблизительно известны заранее. Проще всего эти «приблизительные» корни находить, используя графические методы.
Для нахождения корней многочлена существует несколько численных методов: метод итераций, метод хорд и касательных, метод половинного деления, метод секущих.
Метод бисекций (известный еще и как «метод деления отрезка пополам») также является рекурсивным, т.е. предусматривает повторение с учетом полученных результатов.
Суть метода половинного деления заключается в следующем:
- - дана функция F(x);
- - определена допустимая погрешность Q;
- - определен некоторый интервал [ a , b ], точно содержащий решение уравнения.
1) Вычисляем значение координаты Е, беря середину отрезка , т.е.
Е= (a + b) / 2 (3.2)
- 2) Вычисляем значения F(a), F(b), F(E), и осуществляем следующую проверку: Если F(E)>Q, то корень с указанной точностью найден. Если F(E)
- 3) Переходим к пункту 1.
Метод простых итераций (метод последовательных приближений). Заменим уравнение (2.1) эквивалентным ему уравнением
x=(x) (3.3)
можно сделать различными способами, например
х=х+сf(x), c0. (3.4)
Предположим, что выбрано некоторое начальное приближение корня уравнения (3.3). Определим числовую последовательность по формулам
х n+1 =(x n ), n=0,1,2,… (3.5)
Такую последовательность называют итерационной.
Если на отрезке , содержащем х 0 и все последующие приближения х n , nN, функция (x) имеет непрерывную производную "(x) и |"(x)|q<1, то итерационная последовательность (3.5) сходится к единственному на корню уравнения (3.3). Скорость сходимости определяется неравенством
Из этого неравенства, в частности, следует, что скорость сходимости метода простой итерации зависит от величины q: чем меньше q, тем быстрее сходимость.
Следовательно, на практике при нахождении корней методом простой итерации желательно представить уравнение (2.1) в форме (3.3) таким образом, чтобы производная "(x) в окрестности корня по абсолютной величине была, возможно, меньше. Для этого иногда пользуются параметром с из формулы (3.4).
Метод Ньютона (метод касательных). Если известно достаточно хорошее начальное приближение, для которого выполняется неравенство:
то можно вычислить единственный корень уравнения, используя формулу Ньютона
В качестве начального приближения можно использовать границы интервала, причем:
Если на.
На каждой итерации, данного метода, объем вычислений больше чем в методах биссекций и итераций, поскольку приходится находить не только значение функции, но и ее производной. Однако скорость сходимости метода Ньютона значительно выше.
Теорема. Пусть -корень уравнения, т.е. , а и непрерывна. Тогда существует окрестность корня такая, что если начальное приближение принадлежит этой окрестности, то для метода Ньютона последовательность значений сходится к при. Погрешность -го приближения корня можно оценить по формуле:
где - наибольшее значение модуля второй производной на отрезке, - наименьшее значение модуля первой производной на отрезке.
Правило останова:
Метод хорд и касательных (комбинированный). Данный метод основан на построении схематического графика функции, определении интервалов его пересечения с осью абсцисс и последующим «сжатием» этого интервала при помощи строимых хорд и касательных к графику этой функции.
Надо отметить, что существуют также отдельно метод хорд (дает значение корня с недостатком) и метод касательных (с избытком). Однако преимущество комбинированного метода заключается в «двустороннем сжатии» рассматриваемого отрезка.
Рассмотрим следующий случай:
- - дана функция F(x) и построен ее график;
- - определена допустимая погрешность Q
- - на основании графика определен отрезок , на котором график функции пересекает ось абсцисс, следовательно, на этом отрезке существует корень рассматриваемого многочлена (обозначим его через A)
Дальнейший алгоритм сводится к следующим действиям:
- 1) строим касательную к графику функции в точке F(b)
- 2) вычисляем координату х пересечения касательной с осью абсцисс по формуле (3.9) и обозначаем ее через b"
- 3) строим к графику функции хорду, проходящую через точки F(a) и F(b).
- 4) Вычисляем точку пересечения хорды с осью абсцисс по формуле (2) и обозначаем ее через a".
Таким образом мы получаем новый отрезок , который (по определениям хорды и касательной) по прежнему содержит решение уравнения A.
Теперь принимаем отрезок за новый отрезок и повторяем шаги 1-4 до тех пор, пока разность F(b)-F(a) не станет меньше первоначально заложенной погрешности Q. Отметим также, что после этого рекомендуется в качестве искомого решения взять среднее арифметическое F(a) и F(b).
Таким образом, если хорда (касательная) дает значение корня с избытком, то этот корень берется в качестве новой правой границы, а если с недостатком - то левой. В обоих случаях точный корень лежит между точками пересечения хорды и касательной с осью абсцисс.
Замечание к методу хорд и касательных. Так как для решения поставленной задачи требуется отыскание производной функции F(x), метод хорд и касательных достаточно трудно реализуем на программном уровне, т.к. правила вычисления производных в общем виде довольно громоздки для «понимания» ЭВМ; при непосредственном указании производной для каждой степени многочлена память компьютера серьезно загружается, что очень замедляет работу, а задание функции и, соответственно, ее производной непосредственно в программном коде - недопустимо. Однако, используя данный метод, сходимость интервала к корню происходит наиболее быстро, особенно если совместить метод хорд и касательных с методом бисекции, т.к. середина нового отрезка зачастую дает вполне удовлетворительное решение.
Метод секущих. Метод секущих может быть получен из метода Ньютона при замене производной приближенным выражением - разностной формулой:
В формуле (3.8) используются два предыдущих приближения и. Поэтому при заданном начальном значении необходимо вычислить следующее приближение, например, методом Ньютона с приближенной заменой производной по формуле
Алгоритм метода секущих:
1) заданы начальное значение и погрешность. Вычислим
2) для n = 1,2, ….. пока выполняется условие, вычисляем по формуле (3.8).
Постановка задачи
Отделение корней
Уточнение корней
1.2.3.2. Метод итерации
1.2.3.4. Метод хорд
Постановка задачи
Алгебраическими уравнениями
(1.2.1-1)
трансцендентным уравнением
(1.2.1-2)
Итерационное уточнение корней.
На этапе отделения корней решается задача отыскания возможно более узких отрезков , в которых содержится один и только один корень уравнения.
Этап уточнения корня имеет своей целью вычисление приближенного значения корня с заданной точностью. При этом применяются итерационные методы вычисления последовательных приближений к корню: x 0 , x 1 , ..., x n , …, в которых каждое последующее приближение x n+1 вычисляется на основании предыдущего x n . Каждый шаг называется итерацией. Если последовательность x 0 , x 1 , ..., x n , …при n ® ¥ имеет предел, равный значению корня , то говорят, что итерационный процесс сходится.
Существуют различные способы отделения и уточнения корней, которые мы рассмотрим ниже.
Отделение корней
Корень уравнения f(x)=0считается отделенным (локализованным) на отрезке , если на этом отрезке данное уравнение не имеет других корней. Чтобы отделить корни уравнения, необходимо разбить область допустимых значений функции f(x) на достаточно узкие отрезки, в каждом их которых содержится только один корень. Существуют графический и аналитический способы отделения корней.
Уточнение корней
Задача уточнения корня уравнения с точностью , отделенного на отрезке , состоит в нахождении такого приближенного значения корня , для которого справедливо неравенство . Если уравнение имеет не один, а несколько корней, то этап уточнения проводится для каждого отделенного корня.
Метод половинного деления
Пусть корень уравнения f(x)=0 отделен на отрезке , то есть на этом отрезке имеется единственный корень, а функция на данном отрезке непрерывна.
Метод половинного деления позволяет получить последовательность вложенных друг в друга отрезков , , …,,…, , таких что f(a i).f(b i) < 0 , где i=1,2,…,n, а длина каждого последующего отрезка вдвое меньше длины предыдущего:
Последовательное сужение отрезка вокруг неизвестного значения корня обеспечивает выполнение на некотором шаге n неравенства |b n - a n | < e. Поскольку при этом для любого хÎ будет выполняться неравенство | - х| <, то с точностью любое
Может быть принято за приближенное значение корня, например его середину отрезка
В методе половинного деления от итерации к итерации происходит последовательное уменьшение длины первоначального отрезка в два раза (рис. 1.2.3-1). Поэтому на n-м шаге справедлива следующая оценка погрешности результата:
(1.2.3-1)
где - точное значение корня, х n Î – приближенное значение корня на n-м шаге.
Сравнивая полученную оценку погрешности с заданной точностью , можно оценить требуемое число шагов:
(1.2.3-2)
Из формулы видно, что уменьшение величины e (повышение точности) приводит к значительному увеличению объема вычислений, поэтому на практике метод половинного деления применяют для сравнительно грубого нахождения корня, а его дальнейшее уточнение производят с помощью других, более эффективных методов.
 |
Рис. 1.2.3-2. Схема алгоритма метода половинного деления
Схема алгоритма метода половинного деления приведена на рис. 1.2.3-2. В приведенном алгоритме предполагается, что левая часть уравнения f(x)оформляется в виде программного модуля.
Пример 1.2.3-1. Уточнить корень уравнения x 3 +x-1=0 с точностью =0.1, который локализован на отрезке .
Результаты удобно представить с помощью таблицы 1.2.3-3.
Таблица 1.2.3-3
| k | a | b | f(a) | f(b) | (a+b)/2 | f((a+b)/2) | a k | b k |
| -1 | 0.5 | -0.375 | 0.5 | |||||
| 0.5 | -0.375 | 0.75 | 0.172 | 0.5 | 0.75 | |||
| 0.5 | 0.75 | -0.375 | 0.172 | 0.625 | -0.131 | 0.625 | 0.75 | |
| 0.625 | 0.75 | -0.131 | 0.172 | 0.688 | 0.0136 | 0.625 | 0.688 |
После четвертой итерации длина отрезка |b 4 -a 4 | = |0.688-0.625| = 0.063 стала меньше величины e , следовательно, за приближенное значение корня можно принять значение середины данного отрезка: x = (a 4 +b 4)/2 = 0.656.
Значение функции f(x) в точке x = 0.656 равно f(0.656) = -0.062.
Метод итерации
Метод итераций предполагает замену уравнения f(x)=0 равносильным уравнением x=j(x). Если корень уравнения отделен на отрезке , то исходя из начального приближения x 0 Î, можно получить последовательность приближений к корню
x 1 = j(x 0), x 2 = j(x 1), …, , (1.2.3-3)
где функция j(x) называется итерирующей функцией.
Условие сходимости метода простой итерации определяется следующей теоремой.
Пусть корень
х* уравнения
x=j(x) отделен на отрезке
и построена последовательность приближений по правилу
x n =j(x n -1).
Тогда, если все члены последовательности
x n =j(x n -1) Î и существует такое
q (0
Таким образом, если выполняется условие сходимости метода итераций, то последовательность x 0 , x 1 , x 2 , …, x n ,…, полученная с помощью формулы x n +1 = j(x n ), сходится к точному значению корня :
Условие j(x)Î при xÎ означает, что все приближения x 1 , x 2 , …, x n ,…, полученные по итерационной формуле, должны принадлежать отрезку , на котором отделен корень.
Для оценки погрешности метода итерации справедливо условие
За число q можно принимать наибольшее значение |j"(x)|, а процесс итераций следует продолжать до тех пор, пока не выполнится неравенство
(1.2.3-5)
На практике часто используется упрощенная формула оценки погрешности. Например, если 0 |x n -1 - x n | £ . Использование итерационной формулы x n +1 = j(x n) позволяет получить значение корня уравнения f(x)=0 с любой степенью точности.
Геометрическая иллюстрация метода итераций
. Построим на плоскости X0Y графики функций y=x и y=j(x).
Корень уравнения х=j(x) является абсциссой точки пересечения графиков функции y = j(x)
и прямой y=x. Возьмем некоторое начальное приближение x 0 Î . На кривой y = j(x) ему соответствует точка А 0 = j(x 0). Чтобы найти очередное приближение, проведем через точку А 0 прямую горизонтальную линию до пересечения с прямой y = x (точкаВ 1) и опустим перпендикуляр до пересечения с кривой (точкаА 1), то есть х 1 =j(x 0).
Продолжив построение аналогичным образом, имеем ломаную линию А 0 , В 1 , А 1 , В 2 , А 2 …, для которой общие абсциссы точек представляют собой последовательное приближение х 1 , х 2 , …, х n («лестницу») к корню х*. Из рис. 1.2.3-3а видно, что процесс сходится к корню уравнения. Рассмотрим теперь другой вид кривой y = j(x) (рис. 1.2.6b). В данном случае ломаная линия А 0 , В 1 , А 1 , В 2 , А 2 …имеет вид “спирали”. Однако, и в этом случае наблюдается сходимость. Нетрудно видеть, что в первом случае для производной выполняется условие 0< j’(x)< 1, а во втором случае производная j’(x)<0иj’(x)>-1. Таким образом, очевидно, что если |j’(x)|<1, то процесс итераций сходится к корню. Теперь рассмотрим случаи, когда |j’(x) |> 1. На рис. 1.2.3-4а показан случай, когда j’(x)>1, а на рис. 1.2.3-4b – когда j’(x) < -1. В обоих случаях процесс итерации расходится, то есть, полученное на очередной итерации значение х все дальше удаляется от истинного значения корня. Способы улучшения сходимости процесса итераций
. Рассмотрим два варианта представления функции j(x) при переходе от уравнения f(x)кx=j(x). 1.
Пусть функция j(x) дифференцируема и монотонна в окрестностях корня и существует числоk £ |j‘(x)|, где k ³ 1 (т.е. процесс расходится). Заменим уравнение х=j(x) эквивалентным ему уравнением х=Y(х)
, где Y(х) = 1/j(x)
(перейдем к обратной функции). Тогда 2.
Представим функцию j(x) как j(x) = х - lf(x), где l - коэффициент,
не равный нулю. Для того чтобы процесс сходился, необходимо, чтобы и процесс будет сходящимся, рекуррентная формула имеет вид Если f¢(x) < 0, то в рекуррентной формуле f(x) следует умножить на -1
. Параметр λ может быть также определен по правилу: Если , то , а если , то , где Схема алгоритма метода итерации приведена на рис. 1.2.3-5. Исходное уравнение f(x)=0преобразовано к виду, удобному для итераций: Левая часть исходного уравнения f(x) и итерирующая функция fi(x) в алгоритме оформлены в виде отдельных программных модулей. Рис. 1.2.3-5. Схема алгоритма метода итерации Пример 1.2.3-2. Уточнить корень уравнения 5x – 8∙ln(x) – 8 =0 с точностью 0.1, который локализован на отрезке .
Приведем уравнение к виду, удобному для итераций: Следовательно, за приближенное значение корня уравнения принимаем значение x 3 =3.6892, обеспечивающее требуемую точность вычислений. В этой точке f(x 3)=0.0027. Метод хорд
Геометрическая интерпретация метода хорд
состоит в следующем Проведем отрезок прямой через точки A и B. Очередное приближение x 1 является абсциссой точки пересечения хорды с осью 0х. Построим уравнение отрезка прямой: Положим y = 0 и найдем значение х = х 1 (очередное приближение): Повторим процесс вычислений для получения очередного приближения к корню - х 2 :
В нашем случае (рис.1.2.11) и расчетная формула метода хорд будет иметь вид Эта формула справедлива, когда за неподвижную точку принимается точка b, а в качестве начального приближения выступает точка a. Рассмотрим другой случай (рис. 1.2.3-9), когда . Уравнение прямой для этого случая имеет вид Очередное приближение х 1 при y = 0 Тогда рекуррентная формула метода хорд для этого случая имеет вид Следует отметить, что за неподвижную точку в методе хорд выбирают тот конец отрезка , для которого выполняется условие f (x)∙ f¢¢ (x)>0. Таким образом, если за неподвижную точку приняли точку а,
то в качестве начального приближения выступает х 0 = b, и наоборот. Достаточные условия, которые обеспечивают вычисление корня уравнения f(x)=0 по формуле хорд, будут теми же, что и для метода касательных (метод Ньютона), только вместо начального приближения выбирается неподвижная точка. Метод хорд является модификацией метода Ньютона. Разница состоит в том, что в качестве очередного приближения в методе Ньютона выступает точка пересечения касательной с осью 0Х, а в методе хорд – точка пересечения хорды с осью 0Х – приближения сходятся к корню с разных сторон. Оценка погрешности метода хорд определяется выражением Условие окончания процесса итераций по методу хорд В случае, если M 1 <2m 1 , то для оценки погрешности метода может быть использована формула | x n - x n -1 | £ e.
Пример 1.2.3-4. Уточнить корень уравнения e x – 3x = 0, отделенный на отрезке с точностью 10 -4 .
Проверим условие сходимости: Следовательно, за неподвижную точку следует выбрать а=0, а в качестве начального приближения принять х 0 =1, поскольку f(0)=1>0 и f(0)*f"(0)>0. Результаты расчета, полученные с использованием формулы Таблица 1.2.3-4 Рис. 1.2.3-10. Схема алгоритма метода хорд Нелинейное уравнение – это
1)
алгебраическое или трансцендентное уравнение 2)
алгебраическое уравнение 3)
тригонометрическое уравнение 4)
трансцендентное уравнение Тема 1.2. Методы решения нелинейных уравнений
Постановка задачи
Отделение корней
1.2.2.1. Графическое отделение корней 1.2.2.2. Аналитическое отделение корней Уточнение корней
1.2.3.1. Метод половинного деления 1.2.3.2. Метод итерации 1.2.3.3. Метод Ньютона (метод касательных) 1.2.3.4. Метод хорд 1.2.3.5. Сравнение методов решения нелинейных уравнений 1.2.4. Тестовые задания по теме «Методы решения нелинейных уравнений»
Постановка задачи
Одной из важнейших и наиболее распространенных задач математического анализа является задача определения корней уравнения с одним неизвестным, которое в общем виде можно представить как f(x) = 0. В зависимости от вида функции f(x)различают алгебраические и трансцендентные уравнения. Алгебраическими уравнениями
называются уравнения, в которых значение функции f(x)представляет собой полином n-й степени: f(x) = Р(х) = a n x n + a 2 x 2 + …+ a 1 x + a 0 = 0.(1.2.1-1) Всякое неалгебраическое уравнение называется трансцендентным уравнением
. Функция f(x) в таких уравнениях представляет собой хотя бы одну из следующих функций: показательную, логарифмическую, тригонометрическую или обратную тригонометрическую. Решением уравнения f(x)=0называется совокупность корней, то есть такие значения независимой переменной , при которых уравнение обращается в тождество . Однако, точные значения корней могут быть найдены аналитически только для некоторых типов уравнений. В частности, формулы, выражающие решение алгебраического уравнения, могут быть получены лишь для уравнений не выше четвертой степени. Еще меньше возможностей при получении точного решения трансцендентных уравнений. Следует отметить, что задача нахождения точных значений корней не всегда корректна. Так, если коэффициенты уравнения являются приближенными числами, точность вычисленных значений корней заведомо не может превышать точности исходных данных. Эти обстоятельства заставляют рассматривать возможность отыскания корней уравнения с ограниченной точностью (приближенных корней). Задача нахождения корня уравнения с заданной точностью ( >0)считается решенной, если вычислено приближенное значение , которое отличается от точного значения корня не более чем на значение e (1.2.1-2) Процесс нахождения приближенного корня уравнения состоит из двух этапов: 1) отделение корней (локализация корней);
Уравнения, в которых содержатся неизвестные функции, произведенные в степень больше единицы, называются нелинейными. Системой нелинейных уравнений считается одновременное решение нескольких нелинейных уравнений с одной или несколькими переменными. Существует множество методов решения нелинейных уравнений
и систем нелинейных уравнений, которые принято относить в 3 группы: численные, графические и аналитические. Аналитические методы позволяют определить точные значения решения уравнений. Графические методы наименее точны, но позволяют в сложных уравнениях определить наиболее приближенные значения, с которых в дальнейшем можно начинать находить более точные решения уравнений. Численное решение нелинейных уравнений предполагает прохождения двух этапов: отделение корня и его уточнение до определенно заданной точности. Рассмотрим несколько методов уточнения корней с определенно заданной точностью. Метод половинного деления.
Суть метода половинного деления заключается в делении интервала пополам (с=(a+b)/2) и отбрасывании той части интервала, в которой отсутствует корень, т.е. условие F(a)xF(b) Рис.1. Использование метода половинного деления при решении нелинейных уравнений. Рассмотрим пример. Рис.2. Таблица результатов вычислений В результате вычислений получаем значение с учетом требуемой точности, равной x=-0,946 Метод хорд.
При использовании метода хорд, задается отрезок , в котором есть только один корень с установленной точностью e. Через точки в отрезке a и b, которые имеют координаты (x(F(a);y(F(b)), проводится линия (хорда). Далее определяются точки пересечения этой линии с осью абсцисс (точка z). Рис.3. Использование метода хорд при решении нелинейных уравнений. Рассмотрим пример.
Необходимо решить уравнение х^3 – 0,2x^2 + 0,5x + 1,5 = 0 с точностью до e В общем виде уравнение имеет вид: F(x)= х^3 – 0,2x^2 + 0,5x + 1,5 Найдем значения F(x) на концах отрезка : F(-1) = - 0,2>0; Определим вторую производную F’’(x) = 6x-0,4. F’’(-1)=-6,4 На концах отрезка условие F(-1)F’’(-1)>0 соблюдается, поэтому для определения корня уравнения воспользуемся формулой: Весь произведенный расчет отражен ниже в таблице. Рис.4. Таблица результатов вычислений В результате вычислений получаем значение с учетом требуемой точности, равной x=-0,946 Метод касательных (Ньютона)
Данный метод основывается на построении касательных к графику, которые проводятся на одном из концов интервала . В точке пересечения с осью X (z1) строится новая касательная. Данная процедура продолжается до тех пор, пока полученное значение не будет сравним с нужным параметром точности e (F(zi) Рис.5. Использование метода касательных (Ньютона) при решении нелинейных уравнений. Рассмотрим пример.
Необходимо решить уравнение х^3 – 0,2x^2 + 0,5x + 1,5 = 0 с точностью до e В общем виде уравнение имеет вид: F(x)= х^3 – 0,2x^2 + 0,5x + 1,5 Определим первую и вторую производные: F’(x)=3x^2-0,4x+0,5, F’’(x)=6x-0,4; F’’(-1)=-6-0,4=-6,4 Где x0=b, F(a)=F(-1)=-0,2 Весь произведенный расчет отражен ниже в таблице. Рис.6. Таблица результатов вычислений В результате вычислений получаем значение с учетом требуемой точности, равной x=-0,946 Рассмотрим задачу нахождения корней нелинейного уравнения Корнями уравнения (1) называются такие значения х, которые при подстановке обращают его в тождество. Только для простейших уравнений удается найти решение в виде формул, т.е. аналитическом виде. Чаще приходится решать уравнения приближенными методами, наибольшее распространение среди которых, в связи с появлением компьютеров, получили численные методы. Алгоритм нахождения корней приближенными методами можно разбить на два этапа. На первом изучается расположение корней и проводится их разделение. Находится область , в которой существует корень уравнения или начальное приближение к корню x 0 . Простейший способ решения этой задачи является исследование графика функции f(x) . В общем же случае для её решения необходимо привлекать все средства математического анализа. Существование на найденном отрезке , по крайней мере, одного корня уравнения (1) следует из условия Больцано: f(a)*f(b)<0 (2) При этом подразумевается, что функция f(x) непрерывна на данном отрезке. Однако данное условие не отвечает на вопрос о количестве корней уравнения на заданном отрезке . Если же требование непрерывности функции дополнить ещё требованием её монотонности, а это следует из знакопостоянства первой производной, то можно утверждать о существовании единственного корня на заданном отрезке. При локализации корней важно так же знание основных свойств данного типа уравнения. К примеру, напомним, некоторые свойства алгебраических уравнений: где вещественные коэффициенты. На втором этапе решения уравнения (1), используя полученное начальное приближение, строится итерационный процесс, позволяющий уточнять значение корня с некоторой, наперед заданной точностью. Итерационный процесс состоит в последовательном уточнении начального приближения. Каждый такой шаг называется итерацией. В результате процесса итерации находится последовательность приближенных значений корней уравнения. Если эта последовательность с ростом n приближается к истинному значению корня x , то итерационный процесс сходится. Говорят, что итерационный процесс сходится, по меньшей мере, с порядком m, если выполнено условие: где С>0 некоторая константа. Если m=1 , то говорят о сходимости первого порядка; m=2 - о квадратичной, m=3 - о кубической сходимостях. Итерационные циклы заканчиваются, если при заданной допустимой погрешности выполняются критерии по абсолютным или относительным отклонениям: или малости невязки: Эта работа посвящена изучению алгоритма решения нелинейных уравнений с помощью метода Ньютона. Кафедра: АСОИиУ Лабораторная Работа
На тему: НАХОЖДЕНИЕ КОРНЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ. МЕТОДЫ РЕШЕНИЯ СИСТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
Москва, 2008 год НАХОЖДЕНИЕ КОРНЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ
1. Постановка задачи
Пусть задана функция , непрерывная вместе со своими несколькими производными. Требуется найти все или некоторые вещественные корни уравнения Данная задача распадается на несколько подзадач. Во-первых, необходимо определить количество корней, исследовать их характер и расположение. Во-вторых, найти приближенные значения корней. В-третьих, выбрать из них интересующие нас корни и вычислить их с требуемой точностью e. Первая и вторая задачи решаются, как правило, аналитическими или графическими методами. В случае, когда ищутся только вещественные корни уравнения (1), полезно составить таблицу значений функции . Если в двух соседних узлах таблицы функция имеет разные знаки, то между этими узлами лежит нечетное число корней уравнения (по меньшей мере, один). Если эти узлы близки, то, скорее всего, корень между ними только один. Найденные приближенные значения корней можно уточнить с помощью различных итерационных методов. Рассмотрим три метода: 1) метод дихотомиии (или деление отрезка пополам); 2) метод простой итерации и 3) метод Ньютона. 2. Методы решения задачи
2.1 Метод деления отpезка пополам
Наиболее простым методом, позволяющим найти корень нелинейного уравнения (1), является метод половинного деления. Пусть на отрезке задана непрерывная функция Если значения функции на концах отрезка имеют разные знаки, т.е. Итак, алгоритм метода дихотомии: 1. Задать отрезок и погрешность e. 2. Если f(a) и f(b) имеют одинаковые знаки, выдать сообщение о невозможности отыскания корня и остановиться. Рис.1. Метод деления отрезка пополам для решения уравнения вида f(х)=0. 3. В противном случае вычислить c=(a+b)/2 4. Если f(a) и f(c) имеют разные знаки, положить b=c, в противном случае a=c. 5. Если длина нового отрезка , то вычислить значение корня c=(a+b)/2 и остановиться, в противном случае перейти к шагу 3. Так как за N шагов длина отрезка сокращается в 2 N
раз, то заданная погрешность отыскания корня e будет достигнута за итераций. Как видно, скорость сходимости мала, но к достоинствам метода относятся простота и безусловная сходимость итерационного процесса. Если отрезок содержит больше одного корня (но нечетное число), то всегда будет найден какой-нибудь один. Замечание. Для определения интервала, в котором лежит корень, необходим дополнительный анализ функции , основанный либо на аналитических оценках, либо на использование графического способа решения. Можно также организовать перебор значений функции в различных точках, пока не встретится условие знакопеременности функции 2.2 Метод простой итерации
При использовании этого метода исходное нелинейное уравнение (1) необходимо переписать в виде Обозначим корень этого уравнения C *
. Пусть известно начальное приближение корня . Подставляя это значение в правую часть уравнения (2), получаем новое приближение и т.д. Для (n+1)- шага получим следующее приближение Таким образом, по формуле (3) получаем последовательность С 0
, С 1
,…,С n
+1
, которая стремиться к корню С *
при n®¥. Итерационный процесс прекращается, если результаты двух последовательных итераций близки, т. е. выполняется условие Исследуем условие и скорость сходимости числовой последовательности {C n
} при n®¥. Напомним определение скорости сходимости. Последовательность {C n
}, сходящаяся к пределу С *
, имеет скорость сходимости порядка a, если при n®¥ выполняется условие Допустим, что имеет непрерывную производную, тогда погрешность на (n+1)-м итерационном шаге e n
+1
=C n
+1
-C *
=g(C n)-g(C *) можно представить в виде ряда e n+1
» C n+1
– C *
= g¢(C *) (C n
-C *) +¼@ g¢(C *) e n
+¼ Таким образом, получаем, что при выполнении условия çg¢(C *) ç<1(6) последовательность (3) будет сходиться к корню с линейной скоростью a=1. Условие (6) является условием сходимости метода простой итерации. Очевидно, что успех метода зависит от того, насколько удачно выбрана функция . Например, для извлечения квадратного корня, т. е. решения уравнения вида x =a 2
, можно положить x=g 1
(x)=a/x (7а) x=g 2
(x)=(x+a/x)/2.(7б) Нетрудно показать, что ½g 1
"
(C)½=1, ½g 2
"
(C)½<1. Таким образом, первый процесс (7а) вообще не сходится, а второй (7б) сходится при любом начальном приближении С 0
>0. Рис. 2. Графическая интерпретация метода простых итераций для решения уравнения вида x=g(х). Построение нескольких последовательных приближений по формуле (3) С 0
, С 1
, …, С n
= C * приведено на рисунке 2. 2.3 Метод Ньютона
В литературе этот метод часто называют методом касательных, а также методом линеаризации. Выбираем начальное приближение С 0
. Допустим, что отклонение С 0
от истинного значения корня С *
мало, тогда, разлагая f(C *) в ряд Тейлора в точке С 0
, получим f(C *) = f(C 0) + f¢(C 0) (C *
-C 0) +¼(8) Если f¢(C 0) ¹ 0 , то в (8) можно ограничится линейными по DC =C-C 0
членами. Учитывая, что f(C *)=0, из (9) можно найти следующее приближение для корня C 1
= C 0
– f (C 0) / f¢(C 0) или для (n+1)-го приближения C n+1
= C n
– f (C n) / f ¢(C n) (9) Для окончания итерационного процесса можно использовать одно из двух условий çC n
+1
– C n
ç çf(C n
+1) ç Исследование сходимости метода Ньютона проводится аналогично предыдущему случаю. Самостоятельно получить, что при выполнении условия ½f ""
(C)/2f"(C)½<1. метод Ньютона имеет квадратичную скорость сходимости (). Рис. 3. Графическая интерпретация метода Ньютона для решения уравнения вида f(х)=0. Построение нескольких последовательных приближений по формуле (9) С 0
, С 1
, …, С n
= C * приведено на рисунке 3. 1. Для заданной функции f(x) · определите число вещественных корней уравнения f(x)=0, место их расположения и приближенные значения (постройте график или распечатайте таблицу значений). · Вычислите один из найденных корней (любой) с точностью e=0,5*10 -3
. Для вычислений используйте метод деления отрезка пополам (определите число итераций), а затем этот же корень найдите с помощью метода Ньютона (также определив число итерационных шагов). Сравните полученные результаты. Варианты заданий 1. x 3
–3x 2
+6x – 5 = 0 2. x 3
+sinx –12x-1=0 3. x 3
–3x 2
–14x – 8 = 0 4. 3x + cos x + 1 =0 5. x 2
+4sin x –1 = 0 6. 4x –ln x = 5 7. x 6
–3x 2
+x – 1 = 0 8. x 3
– 0.1x 2
+0.3x –0.6 = 0 9. 11. 13. x 3
–4x 2
–10x –10 = 0 14. 15. 16. 19. 20. 23. 24. x 4
- 2.9x 3
+0.1x 2
+ 5.8x - 4.2=0 25. x 4
+2.83x 3
- 4.5x 2
-64x-20=0 26. МЕТОДЫ РЕШЕНИЯ СИСТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
1.
Постановка задачи
Пусть требуется решить систему n нелинейных уравнений: Прямых методов решения системы (1) не существует. Лишь в отдельных случаях эту систему можно решить непосредственно. Например, для случая двух уравнений иногда удаётся выразить одну неизвестную переменную через другую и таким образом свести задачу к решению одного нелинейного уравнения относительно одного неизвестного. Систему уравнений (1) можно кратко записать в векторном виде: Уравнение (2) может иметь один или несколько корней в области определения D. Требуется установить существование корней уравнения и найти приближённые значения этих корней. Для нахождения корней обычно применяют итерационные методы, в которых принципиальное значение имеет выбор начального приближения. Начальное приближение иногда известно из физических соображений. В случае двух неизвестных начальное приближение можно найти графически: построить на плоскости (x 1
, x 2) кривые f 1
(x 1
, x 2)=0 и f 2
(x 1
, x 2)=0 и найти точки их пересечения. Для трех и более переменных (а также для комплексных корней) удовлетворительных способов подбора начального приближения нет. Рассмотрим два основных итерационных метода решения системы уравнений (1), (2) - метод простой итерации и метод Ньютона. 2. Методы решения системы нелинейных уравнений
2.1.Метод простой итерации
Представим систему (1) в виде или в векторной форме: Алгоритм метода простой итерации состоит в следующем. Выберем некоторое нулевое приближение Следующее приближение находим по формулам: или более подробно: Итерационный процесс (5) продолжается до тех пор, пока изменения всех неизвестных в двух последовательных итерациях не станут малыми, т.е. На практике часто вместо последнего условия используют неравенство: где - среднеквадратичная норма n-мерного вектора При использовании данного метода успех во многом определяется удачным выбором начального приближения : оно должно быть достаточно близким к истинному решению. В противном случае итерационный процесс может не сойтись. Если процесс сходится, то его скорость сходимости является линейной. 2.2. Метод Ньютона
В переводной литературе можно встретить название метод Ньютона-Рафсона. Этот метод обладает гораздо более быстрой сходимостью, чем метод простой итерации. Пусть известно некоторое приближение к корню , так что Тогда исходную систему (2) можно записать следующим образом: Разлагая уравнение (7) в ряд Тейлора в окрестности точки и ограничиваясь линейными членами по отклонению , получим: или в координатной форме: Систему (8) можно переписать в виде: Полученная система (9) является системой линейных алгебраических уравнений относительно приращений Значение функций F 1
, F 2
, …, F n
и их производные в (9) вычисляются при Определителем системы (9) является якобиан J: Для существования единственного решения системы уравнений (9) он должен быть отличен от нуля. Решив систему (9), например, методом Гаусса, найдём новое приближение: Проверяем условие (6). Если оно не удовлетворяется, находим и якобиан (10) с новым приближением и опять решаем (9), таким образом, находим 2-е приближение и т.д. Итерации прекращаются, как только выполнится условие (6). Используя метод Ньютона, найдите решения системы нелинейных уравнений с заданной точностью . Исследуйте сходимость итерационного процесса. Варианты заданий 1 3 5 7 9 11 13 15. 17. 19. 21. 
а значит q=1/k < 1 и процесс будет сходиться.
0<|j¢(x)| = |1 - lf¢(x)| < 1. Возьмем l= 2/(m 1 +M 1 ),
где m 1 и M 1 – минимальное и максимальное значения f’(x) (m 1 =min|f’(x)|, M 1 =max|f’(x)|) для хÎ, т.е. 0£ m 1 £ f¢(x) £ M 1 £1. Тогда
.
(рис.1.2.3-8).
(1.2.3-15)
(1.2.3-16)
1.2.3-14, представлены в таблице 1.2.3-4.
Например, y=ax+b – линейное уравнение, х^3 – 0,2x^2 + 0,5x + 1,5 = 0 – нелинейное (в общем виде записывается как F(x)=0).
Отделение корней осуществляется различными способами: графически, при помощи различных специализированных компьютерных программ и др.Методы численного решения нелинейных уравнений
Разделим отрезок на 2 части: (a-b)/2 = (-1+0)/2=-0,5.
Если произведение F(a)*F(x)>0, то начала отрезка a переносится в x (a=x), иначе, конец отрезка b переносится в точку x (b=x). Полученный отрезок делим опять пополам и т.д. Весь произведенный расчет отражен ниже в таблице.
Если F(a)xF(z)
F’’(0)=-0,4
F’’(0)=-0,4
Условие F(-1)F’’(-1)>0 выполняется, поэтому расчеты производим по формуле: 
то это означает, что внутри данного отрезка находится нечетное число корней. Пусть для определенности корень один. Суть метода состоит в сокращении на каждой итерации вдвое длины отрезка. Находим середину отрезка (см. рис. 1) 
Вычисляем значение функции и выбираем тот отрезок, на котором функция меняет свой знак. Новый отрезок вновь делим пополам. И этот процесс продолжаем до тех пор, пока длина отрезка не сравняется с наперед заданной погрешностью вычисления корня e. Построение нескольких последовательных приближений по формуле (3) приведено на рисунке 1.
(3)
(4)
10. (x -1) 3
+ 0.5e x
= 0
12. x 5
–3x 2
+ 1 = 0
(1)
. (2)
(3)
(4)
(5)
(6)
, т.е.
(8)
(9)
.
(10)
.
2
4
6
8
10
12
14. 
16. 
18. 
20. 
22. 
