Решение нелинейных уравнений.

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

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

. (2.1)

Корнем уравнения называется такое значение аргумента х₀, при котором это уравнение обращается в тождество. Графически корень уравнения соответствует значению аргумента х₀, при котором график функции пересекает ось абсцисс.

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

или , (2.2)

где e - некоторая положительная достаточно малая величина. Попытка поиска точного решения или, что то же самое, задание в программе e=0 приводит к зацикливанию вычислительной программы.

Будем считать, что функция f (x) на интервале [ a,b ] непрерывна. При этом функция может не быть гладкой, т.е. содержать изломы, но на этом интервале не должна иметь разрывов.

Задача распадается на несколько отдельных задач:

1) оценить диапазон определения функции (диапазон значений, которые может принимать аргумент);

2) исследовать количество, характер и расположение корней;

3) найти приближенные значения корней;

4) выбрать из них интересующие и вычислить их с требуемой точностью.

Зависимость f (x) может выражаться с помощью системы уравнений и не иметь аналитического вида. Однако и в этом случае мы должны иметь возможность для любого х из допустимого диапазона найти соответствующее ему значение f (x).

2.2. Выбор диапазона поиска.

Если аналитический вид уравнения известен, то первая задача решается путем анализа вида функции f (x). Например, в уравнении

х не может принимать значения, равные или меньше -3, т.к. логарифм нуля и отрицательных чисел не существует.

В уравнении

х должен быть больше нуля, в уравнении

,

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

Если аналитический вид функции не известен, то проблема нахождения области определения функции становится более сложной. Здесь могут оказаться полезными сведения о физических условиях задачи. Например, при описании процесса движения воды при давлении, близком к атмосферному, ее температура ограничена пределами 0-100°С.

2.3. Выделение корней.

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

Блок-схема процедуры определения интервала приведена на рис.2.1.

Сначала задается интервал [ a,b ], внутри и на границах которого существует функция f (x) и может находиться один из корней. Тут же указывается шаг поиска dx. Затем вычисляется значение функции на левой границе интервала в точке а и организуется цикл, в котором рассчитывается значение функции на расстоянии dx от точки а. Если на участке [ a,a+dx ] функция поменяла знак или приняла нулевое значение, т.е. произведение f(a)*f(b)£0, то это означает, что внутри участка [ a,a+dx ] существует корень уравнения. Если по условиям задачи требуется найти только один корень, то цикл на этом прекращается и производится вычисление корня с требуемой точностью одним из рассмотренных ниже методов. Если необходимо найти все корни уравнения, то выделение участков, содержащих корни, продолжается по аналогичной схеме.

При f (a) *f (b)>0 первоначальный интервал уменьшается на величину шага dx и проверяется, не достигла ли точка а правой границы интервала. Если этого не произошло, то цикл повторяется. Случай, когда был пройден весь интервал [ a,b ] и ни разу функция не поменяла знак, означает, что на данном интервале ни один корень уравнения не найден. При этом расчет приостанавливается и на экран компьютера выводится соответствующее сообщение.

Такая ситуация может быть обусловлена двумя причинами:

1) на интервале [ a,b ] действительно нет корней, в этом случае в зависимости от поставленной задачи необходимо согласиться с полученным сообщением или указать другой интервал поиска;

2) на интервале [ a,b ] существует четное количество корней, при этом была выбрана слишком большая ширина участков и парные корни оказались внутри одного участка. В этом случае можно повторить поиск с меньшим значением dx.

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

Приближенные значения корней уточняют различными итерационными методами, предполагающими последовательное приближение к искомому значению при выполнении однотипных операций. Если заранее известен интервал [ a,b ], на котором функция меняет знак, т.е. выполняется условие , то наиболее надежным является метод половинного деления. Блок-схема метода приведена на рис. 2.2.

Для определения корня этим методом необходимо указать интервал [ a,b ], на котором функция меняет знак, и допустимую погрешность e. Затем вычисляются значения функции на границах интервала f (a) и f (b). После этого организуется цикл, в котором вычисляются середина интервала c= (a+b)/ 2 и значение функции f (c). Далее проверяется условие . При его выполнении принимается, что точка с является корнем уравнения, на экран выводится соответствующее сообщение и расчет прекращается. Если значение функции в точке с по абсолютной величине превосходит допустимую погрешность e, то из двух половин выбирается та, на которой функция меняет знак, и цикл повторяется.

Метод половинного деления прост и надежен, к корню расчет сходится при любых непрерывных функциях f (x), в том числе и недифференцируемых, при этом метод устойчив к ошибкам округления. Скорость сходимости невелика, за одну итерацию интервал неопределенности [ a,b ] сокращается вдвое, зато точность расчета гарантируется.

Недостатки метода:

1. Для начала расчета необходимо найти отрезок, на котором функция меняет знак.

2. Если на этом отрезке несколько корней, то заранее неизвестно, к какому из корней сойдется процесс, хотя к одному из них обязательно сойдется.

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

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

2.5. Метод хорд.

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

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

откуда

. (2.3)

Блок-схема метода хорд приведена на рис.2.4. Она почти полностью повторяет блок-схему метода половинного деления. Отличия заключаются в расчете по иной формуле координаты точки с для дальнейшего уточнения корня и дополнительных переприсвоениях значений функций f (a)= f (c) или f (b)= f (c) при сокращении интервала неопределенности.

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

2.6. Метод Ньютона.

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

На рис.2.5. показана схема итерационных вычислений корня уравнения по методу Ньютона. Для начала расчета должны быть заданы начальная точка x₀ и допустимая погрешность e. В точке x₀ вычисляются значения функции f (x) и ее производной . Далее функция f (x) аппроксимируется ее производной, новое приближение к корню определяется как точка пересечения касательной с осью абсцисс. Значение производной в точке x₀ равно

,

откуда находится координата точки x₁:

.

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

(2.4)

до тех пор, пока не будет выполнено условие (2.2).

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

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

Согласно (2.4) получим формулу

,

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

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

2.7. Метод секущих.

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

Значение производной можно вычислить приблизительно по значениям функции в двух точках x₁ и x₂, как это показано на рис.2.8.

Заменив в формуле (2.4.) производную ее приближенным значением

,

получим новую формулу для определения следующего приближения к корню

(2.5)

Блок-схема метода секущих представлена на рис.2.9.

Для начала процесса надо задать две точки x₁ и x₂ и допустимую погрешность e. По сравнению с методом Ньютона из-за погрешности в определении производной для нахождения корня требуется выполнить большее количество шагов. Однако в методе секущих на каждом шаге вычисляется только одно значение функции, в то время как в методе –Ньютона вычисляются значения функции и ее производной, поэтому скорость счета у них приблизительно одинакова. Недостаток метода секущих связан с тем, что в знаменателе формулы (2.5) стоит разность значений функции. Вдали от корня это несущественно, но вблизи от корня значения функции малы и очень близки. В результате этого возникает потеря значащих цифр, приводящая к «разболтке» счета, когда результаты вычисления начинают колебаться около истинного значения, не сходясь к нему. Это ограничивает точность счета.

От «разболтки» страхуются так называемым приемом Гарвика. Выбирают не очень малое e₁, ведут итерации до выполнения условия и затем продолжают расчет до тех пор, пока убывают. Первое же возрастание обычно означает начало «разболтки», тогда расчет прекращают и последнюю итерацию не используют.

Следует отметить еще одну сторону метода секущих. Формула (2.5) идентична формуле (2.3) метода хорд:

.

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

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

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

Численное значение определенного интеграла определяется по формуле

,

где a, b – пределы интегрирования; f (x) – подинтегральная функция;

F (x) – первообразная подинтегральной функции f (x).

В практических задачах достаточно редко удается найти точное аналитическое решение, поэтому приходится прибегать к приближенному численному интегрированию. Для этого обычно заменяют функцию f (x) на близкую к ней и совпадающую с ней в ряде точек функцию j(x), для которой можно найти аналитическое решение. Поскольку на широком интервале [ a,b ] такую функцию подобрать сложно, то исходный интервал разбивают на несколько более узких и вычисляют общий интеграл как сумму интегралов по узким интервалам.

Наиболее часто функцию f (x) заменяют алгебраическим многочленом

.

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

- нулевая степень;

- первая степень;

- вторая степень.

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

Определенный интеграл функции f (x) на отрезке [ a,b ] можно представить как площадь под кривой f (x), ограниченной пределами интегрирования и осью абсцисс. Разобьем отрезок [ a,b ] на n отрезков одинаковой длины

.

В результате получим набор равноудаленных друг от друга точек . Рассмотрим один отрезок [ x_i-1,x_i ].

Для аппроксимации функции f (x) будем использовать полином нулевой степени , где - некоторая постоянная величина, ограниченная значениями f (x_i-1) и f (x_i). Если принять, что величина равна значению f (x_i-1) на левом крае отрезка, то площадь криволинейной трапеции будет приблизительно равна площади заштрихованного на рис.3.1.а прямоугольника

.

Сумма площадей всех прямоугольников даст приближенное значение интеграла:

. (3.1)

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

В качестве величины можно взять значение функции на правой границе отрезка f (x_i). Площадь заштрихованного прямоугольника на рис.3.1.б будет равна

,

а значение интеграла:

. (3.2)

Это формула правых прямоугольников.

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

,

а величина интеграла:

. (3.3)

Это формула средних прямоугольников.

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

Для начала расчета задаются границы интегрирования [ a,b ] и количество подинтервалов n, на которые разбивается основной интервал. Затем в соответствии с выбранным методом интегрирования суммируются значения функции на каждом из подинтервалов. Поскольку длины подинтервалов равны между собой, то величину D x целесообразно вынести за знак суммы и умножить на эту величину окончательную сумму значений функций.

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

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

Блок-схема метода приведена на рис.3.3.

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

Если для аппроксимации функции f (x) взять полином первой степени и поставить условие, чтобы значения функций f (x) и j(x) совпадали на концах подинтервалов, то заштрихованная площадь на рис.3.4. будет равна

,

а вся площадь под кривой, соответствующая значению определенного интеграла,

. (3.4)

Это формула трапеций.

Вычисления по методу трапеций также могут быть организованы как с заданным количеством подинтервалов n, так и с заданной величиной шага D x. В блок-схемах алгоритмов на рис.3.2 и рис.3.3 изменится только узел вычисления интегральной суммы:

или, например, организован цикл:

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

3.4. Метод Симпсона.

Возьмем для аппроксимации функции f (x) многочлен второй степени . Чтобы определить коэффициенты a,b,c, необходимо на интервале аппроксимации задать три точки. Выберем шаг интегрирования D x и вычислим значения функции на концах интервала и в его середине. Обозначим, как это показано на рис.3.5, значения аргумента через x₀, x₁, x₂ и, соответственно, значения функции через f₀, f₁, f₂. Половину шага интегрирования обозначим как .

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

.

Учитывая, что , при интегрировании этой функции в пределах от x₀ до x₀+2h после преобразований получим:

.

Для всего интервала интегрирования будем иметь:

, (3.5)

где .

Это формула Симпсона.

Как и для рассмотренных ранее методов, вычисления интегралов по формуле Симпсона могут быть по блок-схемам рис.3.2 или рис.3.3.

3.5. Погрешность вычислений различных методов.

Точное значение определенного интеграла можно представить в виде

,

где D S_i^мет - площадь элементарной фигуры (прямоугольника, прямолинейной или криволинейной трапеции), вычисленная по какому-либо методу; R^мет – погрешность вычисления этого метода.

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

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

различными методами, точное значение которого до шестого знака после запятой равно 2,718282.

Таблица 3.1

Не нашли, что искали? Воспользуйтесь поиском: