Задание. Напишите процедуры CROUT(N,A) для -факторизации матрицы и SOLVE(A,B,N) для прямой и обратной подстановок

Напишите процедуры CROUT(N,A) для -факторизации матрицы и SOLVE(A,B,N) для прямой и обратной подстановок. Для отладки процедуры можно использовать матрицы

,

В результате должно получиться две матрицы

, ,

а решение имеет вид .

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

Нелинейные уравнения – это алгебраические или трансцендентные уравнения вида

. (1)

Значения , которые обращают функцию в нуль, называются корнями уравнения.

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

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

Одним из важнейших методов решения нелинейных уравнений является метод простых итераций / метод последовательных приближений /. В методе простой итерации уравнение приводится к виду

. (2)

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

(3)

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

. (4)

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

Итак, достаточным условием сходимости итерационного процесса , (2) является выполнение неравенства при всех значениях , вычисляемых в ходе решения задачи.

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

Например, уравнение имеет два корня, в чем легко убедиться, построив графики функций и . Первый из этих корней лежит в интервале , а второй – в интервале . Для определения первого корня записываем исходное уравнение в виде , т.е. , производная функции - . На интервале . В качестве начального приближения можно выбрать . Метод простой итерации дает Точность корня определяется величиной (4). Для нахождения второго корня представляем исходное уравнение в виде , т.е. , производная - . На интервале также, как и в предыдущем случае . В качестве начального приближения можно взять . Метод простой итерации дает

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

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

Эффективным методом повышения точности результатов и ускорения сходимости является метод Ньютона / метод касательных /.

Итерационная последовательность в методе Ньютона строится по формуле

. (5)

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

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

Метод Ньютона имеет простую геометрическую интерпретацию (Рис.2). Через точку проведем касательную до ее пересечения с осью абсцисс. Уравнения касательной - . Точка пересечения касательной с осью абсцисс - и есть следующее приближение для корня .

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

При решении нелинейных уравнений может использоваться также метод половинных делений / метод дихотомии /. Метод применяется для непрерывной функции , принимающей на концах интервала значения разных знаков. При этом дифференцируемости функции не требуется. Отрезок делится пополам. В средней точке , которая может рассматриваться как первое приближение для корня, вычисляется значение функции - . Если , то выбирается тот из интервалов или , на концах которого значения функции различны по знаку. Процесс продолжается до тех пор, пока длина отрезка не станет меньше . Тогда координата середины последнего отрезка и есть корень с заданной точностью. Следует иметь в виду, что шагов деления уменьшают интервал в раз, так 10 шагов уменьшают исходный интервал приблизительно в 1000 раз, т.е. скорость сходимости невелика. Однако в отличие от метода простой итерации и метода Ньютона здесь гарантируется нахождение корня для любых функций, в том числе и для не дифференцируемых. Если на находится несколько корней, то будет найден только один из них. При этом кратные четные корни определить нельзя.

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

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

Поиск по сайту: