Решение нелинейных алгебраических уравнений

Чебоксарский политехнический институт (филиал)

УНИВЕРСИТЕТА МАШИНОСТРОЕНИЯ

Кафедра управления в технических системах и программирования

 

 

 

 

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

 

по дисциплине  Программирование

на тему Решение нелинейных алгебраических уравнений

вариант 10

 

 

 

 

 

 

 

 

 

 

 

 

 

Чебоксары 2015

 

Содержание

Текст задания …………………………………………………………………………..	3
Введение………………………………………………………………………………...	4
Метод хорд……………………………………………………………………………...	5
Метод итераций………………………………………………………………………...	7
методом Горнера (уточнение корней)………………………………………………...	11
Алгоритм выполнения задания в виде блок-схемы……………………………….....	12
Исходный текст программы…………………………………………………………...	13
Сеансы работы программы…………………………………………………………….	18
Заключение……………………………………………………………………………...	19
Список источников..........................................................................................................	20

 

Текст задания

Вариант № 10

Разработать программу «Решение нелинейных алгебраических уравнений» различными методами:

1) методом хорд;

2) методом итераций;

3) методом Горнера (уточнение корней).

 

ВВЕДЕНИЕ

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

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

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

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

 

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

Заменим дугу MM/ кривой - хордой MM/ . Уравнение последней может быть написано, например в виде:

y-f(a) =(x-a). (3)

Наше правило, по существу, сводится к тому, что вместо точки А пересечения кривой с осью x определяется точка D пересечения с осью x этой хорды.

Действительно, полагая в (3) уравнении y=0, а для абсциссы x1 точки D получаем именно выражение вида:

x1 = b-

В связи с этим, правило пропорциональных частей называют также методом хорд. Ну а теперь обратимся к исследованию вопроса о положении точки x1 по отношению к корню . Непосредственно ясно, что точка x1 лежит между a и b, но с какой стороны от ? Выясним это.

Так в случаях I и II (III и IV) мы имеем дело с выпуклой вниз (вверх) функцией, то кривая MM/ лежит под (над) хордойMM/ , то есть

f(x) f(a)+(x-a) (a<x<b) (4)

Полагая здесь x=x1 , непосредственно получаем f(x1)0, так что f(x1) всегда имеет знак противоположный знаку f //(x). Отсюда, наконец, заключаем, что в случаях I и IV значение x1 лежит между a и , в случаях же II и III - между и b.

Ограничиваясь случаями I и IV, применим снова наше правило, на этот раз к промежутку [х1, b], заменяя в (2) а на x1получим новое приближенное значение корня :

x2=x1 - ,

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

a<x1<x2<…<xn<xn+1<…<.

При этом любые два последовательных значения хп и хп+1 связаны формулой, аналогичной (2),

xn+1=xn - (5)

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

, откуда f()=0.

Так как других корней уравнения (1), кроме , в промежутке [а, b] нет, то =*)

Рисунок иллюстрирует постепенное приближение точек D1, D2, ... пересечения последовательных хорд с осью х к искомой точке А. Легко понять, что в случаях II или III повторное применение правила приведет к последовательности убывающих приближенных значений b>x1>x2>… >xn>xn+1>…> стремящихся к корню справа. Таким образом, во всех случаях, применив достаточное число раз указанное выше правило, можно вычислить корень с любой степенью точности. При этом, впрочем, остается открытым вопрос, как оценить точность уже вычисленного приближенного значения хп.

Для решения его применим к разности f(xn)- f() формулу конечных приращений:

f(xn) =f(xn)-f()=(xn- ) f /(c) () cxn).

Отсюда xn-;

если обозначить через т наименьшее значение |f /(x)| в рассматриваемом промежутке (которое можно раз навсегда вычислить наперед), то получим оценку:

|xn-|. (6)

Так по самой величине f(xn) оказывается возможным судить о близости хп к корню!

 

 

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

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

f(x)=0.

(1)

где f(x) – непрерывная функция, и требуется определить его вещественные корни. Заменим уравнение (1) равносильным уравнением

x=j (x).

(2)

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

x1=j (x0).

(3)

Подставляя теперь в правую часть равенства (3) вместо x0 число x1 получим новое число x2=j (x1). Повторяя этот процесс, будем иметь последовательность чисел

xn=j (xn-1) (n=1, 2,...).

(4)

Если эта последовательность – сходящаяся, т.е. существует предел  , то, переходя к пределу в равенстве (4) и предполагая функцию j (x) непрерывной, найдем:

или

x =j (x). (5)

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

Доказано, что достаточными условиями сходимости итерационного процесса является выполнение условия | j (x)<1 для xО [a, ,b].

При этом процесс сходится к единственному корню x .

  

На рис. 1 приведен пример сходящегося итерационного процесса xn+1=j (xn) при 0<j ’(x)<1 и на рис.2 – расходящегося при j ’(x)<1.

Схема Горнера для деления многочлена - это алгоритм упрощения вычисления значения многочлена f(x) при определённой величине x = x0 методом деления многочлена на одночлены (многочлены 1ой степени). Каждый одночлен включает в себя максимум один процесс умножения и один процесс сложения. Результат, полученный из одного одночлена, прибавляют к результату полученному от следующего одночлена и так далее в аккумулятивной манере. Такой процесс деления также называют синтетическим делением.

Чтобы объяснить вышесказанное, давайте перепишем многочлен в развёрнутой форме;

f(x0) = a0 + a1x0 + a2x02 + ... + anx0n

Это также может быть записано как:

f(x0) = a0 + x0(a1 + x0(a2 + x0(a3 + ... + (an-1 + anx0)....)

методом Горнера

Обычно многочлен представлен в виде:

или

f(x) = a0 + a1x + a2x2 + ... + akxk

Где ak это действительные числа, представляющие коэффициенты многочлена и 
xk это переменные многочлена.

Вышеупомянутый многочлен называют многочленом n-ой степени, то есть deg(f(x)) = n, где nпредставляет наивысшую степень переменной.

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

Алгоритм приводится в действие, следуя нижеизложенным шагам:

1. Дано k = n 
2. Пусть bk = ak 
3. Пусть bk - 1 = ak - 1 + bkx0 
4. Пусть k = k - 1 
5. Если k ≥ 0, то вернуться на шаг 3  
иначе Конец

Этот алгоритм может быть также графически визуализирован, принимая во внимание данный многочлен 5ой степени:

f(x) = a0 + a1x + a2x2 + a3x3 + a4x4 + a5x5

значение которого находится как x = x0, путём перестановки его следующим образом:

f(x0) = a0 + x0(a1 + x0(a2 + x0(a3 + x0(a4 + a5x0))))

Другим способом представить результаты используя этот алгоритм можно в виде данной ниже таблицы:

K	5	4	3	2	1	0
	b5 = a5	b4 = a4 + x0b5	b3 = a3 + x0b4	b2 = a2 + x0b3	b1 = a1 + x0b2	b0 = a0 + x0b1

Пример: Найти значение многочлена f(x) = x4 + 3x3 + 5x2 + 7x + 9 at x = 2

Решение:

Так как многочлен 4ой степени, то n = 4

K	4	3	2	1	0
Шаг	b4 = 1	b3 = 3 + 2 * 1	b2 = 5 + 2 * 5	b1 = 7 + 2 * 15	b0 = 9 + 2 * 37
Результат	1	5	15	37	83

Таким образом, f(2) = 83.

Почему нам это необходимо делать?

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

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

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

 

методом Горнера (уточнение корней).

 

 

     Если то при делении f(x) на g(x) частное q(x) имеет вид

где Остаток r находится по формуле

 
Корни многочлена      

Корень многочлена f(x) - число , такое, что

     

Число - k-кратный корень многочлена f(x), если

     

Если число является k-кратным корнем многочлена f(x), то при k > 1 оно будет (k - 1)-кратным корнем первой производной этого многочлена; при k = 1 число не является корнем производной.

 
Разложение многочлена степени n на множители  
 
Многочлен f(x) с комплексными коэффициентами

Здесь - различные корни многочлена кратностей соответственно

 

Алгоритм выполнения задания в виде блок-схемы.

 
Исходный текст программы.

1. методом хорд

 

#include <iostream>

#include <cmath>

 

double func(double x)

{

    return pow(x, 3) - 2 * pow(x, 2) - 6 * x - 1;