Аппроксимация функции к полиному n степени методом наименьших квадратов

Аппроксимация – процесс замены таблично заданной функции аналитическим выражением кривой. Алгоритм нахождения зависимости между заданными переменными. Условия сходимости итераций к решению системы уравнений. Методы Якоби и Гаусса. Тестирование программы.
Краткое сожержание материала:

Размещено на

Введение

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

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

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

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

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

В третьем разделе рассмотрен тест программного модуля.



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

1.1 Математическая модель задачи

Аппроксимация (или упрощение кривыми) - это процесс замены таблично заданной функции y(x) аналитическим выражением кривой g(x), которая необязательно совпадает с допустимой погрешностью. Одним из видов аппроксимации табличных функций является степенной ряд (полином). Для определения коэффициентов в аналитических выражениях используют метод наименьших квадратов, при котором коэффициенты определяются таким образом, что суммарная квадратичная ошибка

в узлах таблицы являются минимальными.

Рассмотрим задачу. Известна таблица (таблица 1) значений двух переменных x и y.

Таблица 1 - Значения x и y

x	x0 x1 x2 … xn-1 xn
y	y0 y1 y2 … yn-1 yn

Требуется найти зависимость между переменными в виде уравнения .

Предполагается, что каждое данное измерено с некоторой неизвестной ошибкой , где - истинное значение.

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

.

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

.

Полученные соотношения - система уравнений для определения параметров .

Очень часто в качестве эмпирической функции используется многочлен степени m:

.

Тогда

;

.



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

,

где .

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

,

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

,

где

.

Предполагается, что матрица А неособенная, т. е. , и решение единственно.

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

где

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

и перепишем систему (1) в виде одного матричного уравнения

(2)

Здесь ax -произведение матрицы a на вектор x.

Последовательные приближения (итерации) найдем следующим образом. Возьмем в качестве начального приближения x(0) вектор в и подставим его в правую часть уравнения (2); получим x(1). Продолжая аналогичные вычисления, придём к векторной последовательности приближений:



Если существует придел о последовательности векторов x(k), то, переходя к пределу в равенстве при k>?, убеждаемся, что о является решением уравнения (2), т. е.

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

Теорема. Если какая либо норма матрицы меньше единицы: ||a||<1, то уравнение (2) имеет единственное решение о, к которому стремится последовательность итераций (3) при любом выборе начального приближения x(0).

В расчетах полагают x(0)=в. Погрешность приблеженного решения уравнения (2) на k-м шаге оценивают неравенством

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

Отклонение приближения x(k) от решения о по норме не будет превышать е, если



Неравенство (5) дает обычно завышенную оценку числа итераций k. В оценках (4), (5) одновременно используются согласованные нормы для матриц и векторов (m- и l-нормы).

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

Замечание. Достаточное условие сходимости для каждого уравнения системы по m-норме можно представить в виде

Здесь модули диагональных коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов. Естественно, что если условия (7) не выполнены, то следует применять условия сходимости по l- и k-нормам после приведения системы к виду (1) или непосредственно к неприведенной системе . Достаточное условие сходимости процесса итераций для неприведенной системы по l-норме можно представить в виде



Если система (8) не решается методом Якоби, то в программе автоматически запускается решение методом Гаусса. Суть его в том, что систему мы преобразуем, исключив сначала неизвестную a1 из второго и последующих уравнений системы. Затем вычитаем уравнение из остальных. В результате получаем систему, в которой неизвестное a1 исключено из последующих уравнений.

Разделив второе уравнение на x2, затем умножив на xn в зависимости от уравнения из которого будим вычитать и так далее пака не получим нижнюю треугольную матрицу.

Таким же методом преобразуем матрицу к диагональному виду.



Итак, решение системы уравнений представляет собой вектор

.

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

Нахождение действительных корней с определенной точностью можно разбить на два этапа:

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

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

Известно, что если функция f(x) непрерывна и принимает на концах отрезка [a,b] значения разных знаков, т. е. f(a)f(b)<0, то внутри этого промежутка

найдется нуль функции.

Пусть требуется решить уравнение, представленное в виде

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

Последовательность

называется последовательностью итераций для уравнения (8) с начальной точкой x(0). Если все точки (9) принадлежат отрезку [a,b] и существует предел то, перейдя к пределу в равенстве

получим

Следовательно, если существует предел последовательности итераций (9), то он является корнем уравнения (8). Достаточные условия сходимости последовательности итераций содержатся в следующей теореме.

Теорема. Пусть функция g(x) имеет на отрезке [a,b] непрерывную производную и выполнены два условия:

-

- значение функции y=g(x) принадлежит отрезку [a,b] для любого .

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

Оценка погрешности k-го приближения x(k) к корню о такова:

где

1.2 Входные данные

Входными данными для решения поставленной задачи является количество точек m, значения координат точек x и...