Ѕаза знаний студента. –еферат, курсова€, контрольна€, диплом на заказ

курсовые,контрольные,дипломы,рефераты

»нтерпол€ци€ многочленами — ћатематика

ѕосмотреть видео по теме –еферата

¬ведение

≈сли задана функци€ y(x), то это означает, что любому допустимому значению х сопоставлено значение у. Ќо нередко оказываетс€, что нахождение этого значени€ очень трудоЄмко. Ќапример, у(х) может быть определено как решение сложной задачи, в которой х играет роль параметра или у(х) измер€етс€ в дорогосто€щем эксперименте. ѕри этом можно вычислить небольшую таблицу значений функции, но пр€мое нахождение функции при большом числе значений аргумента будет практически невозможно. ‘ункци€ у(х) может участвовать в каких-либо физико≠-технических или чисто математических расчЄтах, где еЄ приходитс€ многократно вычисл€ть. ¬ этом случае выгодно заменить функцию у(х) приближЄнной формулой, то есть подобрать некоторую функцию j(х), котора€ близка в некотором смысле к у(х) и просто вычисл€етс€. «атем при всех значени€х аргумента полагают у(х)їj(х).

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

¬ыбрав узловые точки и класс приближающих функций, мы должны ещЄ выбрать одну определЄнную функцию из этого класса посредством некоторого критери€ Ч некоторой меры приближени€ или Ђсогласи€ї. ѕрежде чем начать вычислени€, мы должны решить также, какую точность мы хотим иметь в ответе и какой критерий мы изберЄм дл€ измерени€ этой точности.

¬сЄ изложенное можно сформулировать в виде четырЄх вопросов:

1.  акие узлы мы будем использовать?

2.  акой класс приближающих функций мы будем использовать?

3.  акой критерий согласи€ мы применим?

4.  акую точность мы хотим?

—уществуют 3 класса или группы функций, широко примен€емых в численном анализе. ѕерва€ группа включает в себ€ линейные комбинации функций 1, х, х2, Е, хn, что совпадает с классом всех многочленов степени n (или меньше). ¬торой класс образуют функции cos aix, sin aix. Ётот класс имеет отношение к р€дам ‘урье и интегралу ‘урье. “реть€ группа образуетс€ функци€ми e-az. Ёти функции встречаютс€ в реальных ситуаци€х.   ним, например, привод€т задачи накоплени€ и распада.

„то касаетс€ критери€ согласи€, то классическим критерием согласи€ €вл€етс€ Ђточное совпадение в узловых точкахї. Ётот критерий имеет преимущество простоты теории и выполнени€ вычислений, но также неудобство из-за игнорировани€ шума (погрешности, возникающей при измерении или вычислении значений в узловых точках). ƒругой относительно хороший критерий Ч это Ђнаименьшие квадратыї. ќн означает, что сумма квадратов отклонений в узловых точках должна быть наименьшей возможной или, другими словами, минимизирована. Ётот критерий использует ошибочную информацию, чтобы получить некоторое сглаживание шума. “ретий критерий св€зываетс€ с именем „ебышева. ќсновна€ иде€ его состоит в том, чтобы уменьшить максимальное отклонение до минимума. ќчевидно, возможны и другие критерии.

Ѕолее конкретно ответить на поставленные 4 вопроса можно лишь исход€ из условий и цели каждой отдельной задачи.

»нтерпол€ци€ многочленами

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

ћетоды интерпол€ции Ћагранжа и Ќьютона

ќдин из подходов к задаче интерпол€ции Ч метод Ћагранжа. ќсновна€ иде€ этого метода состоит в том, чтобы прежде всего найти многочлен, который принимает значение 1 в одной узловой точке и 0 во всех других. Ћегко видеть, сто функци€

††††††††††††††††††

€вл€етс€ требуемым многочленом степени n; он равен 1, если x=xj и 0, когда x=xi, i¹j. ћногочлен Lj(x)×yj принимает значени€ yi в i-й узловой точке и равен 0 во всех других узлах. »з этого следует, что †есть многочлен степени n, проход€щий через n+1 точку (xi, yi).

ƒругой подход Ч метод Ќьютона (метод разделЄнных разностей). Ётот метод позвол€ет получить аппроксимирующие значени€ функции без построени€ в €вном виде аппроксимирующего полинома. ¬ результате получаем формулу дл€ полинома Pn, аппроксимирующую функцию f(x):

P(x)=P(x0)+(x-x0)P(x0,x1)+(x-x0)(x-x1)P(x0,x1,x2)+Е+

(x-x0)(x-x1)Е(x-xn)P(x0,x1,Е,xn);

†††††††††††††††††† †Ч разделЄнна€ разность 1-го пор€дка;

†††††††††††††††††† †Ч разделЄнна€ разность 2-го пор€дка и т.д.

«начени€ Pn(x) в узлах совпадают со значени€ми f(x)

‘актически формулы Ћагранжа и Ќьютона порождают один и тот же полином, разница только в алгоритме его построени€.

—плайн-аппроксимаци€

ƒругой метод аппроксимации Ч сплайн-аппроксимаци€ Ч отличаетс€ от полиномиальной аппроксимации Ћагранжем и Ќьютоном. —плайном называетс€ функци€, котора€ вместе с несколькими производными непрерывна на отрезке [a, b], а на каждом частном интервале этого отрезка [xi, xi+1] в отдельности €вл€ютс€ некоторым многочленом невысокой степени. ¬ насто€щее врем€ примен€ют кубический сплайн, то есть на каждом локальном интервале функци€ приближаетс€ к полиному 3-го пор€дка. “рудности такой аппроксимации св€заны с низкой степенью полинома, поэтому сплайн плохо аппроксимируетс€ с большой первой производной. —плайнова€ интерпол€ци€ напоминает лагранжевую тем, что требует только значени€ в узлах, но не еЄ производных.

ћетод наименьших квадратов

ѕредположим, что требуетс€ заменить некоторую величину и делаетс€ n измерений, результаты которых равны xi=x+ei (i=1, 2, Е, n), где ei Ч это ошибки (или шум) измерений, а х Ч истинное значение. ћетод наименьших квадратов утверждает, что наилучшее приближЄнное значение †есть такое число, дл€ которого минимальна сумма квадратов отклонений от :

††††††††††††††††††

ќдин из наиболее общих случаев применени€ этого метода состоит в том, что имеющиес€ n наблюдений (xi, yi) (i=1, 2, Е, n) требуетс€ приблизить многочленом степени m

†††††††††††††††††† y(x)=a0+a1x+a2x2+Е+amxm

¬ычисленна€ крива€ у(х) в некотором смысле даЄт сложное множество значений уi. ћетод наименьших квадратов утверждает, что следует выбирать многочлен, минимизирующий функцию.

†††††††††††††††††† †††††††††† 

ƒл€ нахождени€ минимума дифференцируем  по каждой из неизвестных ak. ¬ результате получим:

††††††††††††††††††

ќпределитель этой системы отличен от нул€ и задача имеет единственное решение. Ќо система степеней не ортогональна, и при больших значени€х n задача плохо обусловлена. Ёту трудность можно обойти, использу€ многочлены ортогональные с заданным весом на заданной системе точек, но к этому прибегают только в задачах, св€занных с особенно тщательной статической обработкой эксперимента.

ѕолиномы „ебышева

 ритерии согласи€ данного метода Ч минимизаци€ максимальной ошибки.

ѕолиномы „ебышева определ€ютс€ следующим образом: Tn(x)=cos(n×arccos(x))

Ќапример:†† T0(x)=cos(0)=1,

†††††††††††††††††† T1(x)=cos(q)=x,

†††††††††††††††††† T2(x)=cos(2q)=cos2(q)-sin2(q)=2x2-1.

ћожно было бы и дальше использовать тригонометрические соотношени€ дл€ нахождени€ полиномов „ебышева любого пор€дка, но будет лучше установить дл€ них рекурентное соотношение, св€зывающее Tn+1(x), Tn(x) и Tn-1(x):

†††††††††††††††††† Tn+1(x)=cos(nq+q)=cos(nq)cos(q)-sin(nq)sin(q),

†††††††††††††††††† Tn-1(x)=cos(nq-q)=cos(nq)cos(q)-sin(nq)sin(q).

—кладыва€ эти неравенства, получим:

†††††††††††††††††† Tn+1(x)+Tn-1(x)=2cos(nq)cos(q)=2xTn(x);

†††††††††††††††††† Tn+1(x)=2xTn(x)-Tn-1(x).

–ис. 1

ѕримен€€ полученные формулы можно найти любой полином „ебышева. Ќапример, “3(x)=2xT2(x)-T1(x). ѕодставл€€ значени€ T2(х) и “1(х) имеем “3(х)=2х(2х2-1)-х=4х3-3х. √рафически первые 10 полиномов „ебышева изображены ниже. ѕоследующие полиномы по-прежнему колеблютс€ между +1 и -1, причЄм период колебани€ уменьшаютс€ с ростом пор€дка полинома.

ѕреобразовани€ q=arccos(x) можно рассматривать как проекцию пересечени€ полукруга с множеством пр€мых, имеющих равные углы между собой (рис.1). “аким образом, множество точек xj, на котором система чебышевских многочленов Tn(x) ортогональна, таково:

†††††††††††††††††† j=0, 1, 2, Е,N-1)

“ак как Tn(x) есть, по существу, cos(nq), то они €вл€ютс€ равноколеблющимес€ функци€ми, и так как они многочлены, то обладают всеми свойствами ортогональных многочленов.

„ебышев показал, что из всех многочленов –n(x) степени n старшим коэффициентом 1, у многочлена †точна€ верхн€€ грань абсолютных значений на интервале -1£x£1 наименьша€. “ак как верхн€€ грань Tn(x)=1, óêàçàííàÿ âåðõíÿÿ ãðàíü ðàâíà .

ѕрактическое задание

Ќа практике нам нужно было изучить приближение нашей функции полиномами “ейлора.

 ак уже упоминалось выше, многочлены “ейлора легко вычисл€ть, а так же превращать в степенные р€ды. ¬ этом мы и убедились на практике.

Ќиже представлена таблица коэффициенты первых 12-и полиномов „ебышева, а также таблица коэффициентов перед полиномами „ебышева, выражающие первые 12 степеней х.

Ёти данные мы получили, использу€ программы на страницах

¬ этих программах использовались следующие алгоритмы:

I.    ѕреобразование коэффициентов полинома „ебышева в коэффициенты традиционного многочлена.

1) ¬водим коэффициенты a0, a1, Е, an многочлена T(x) и образуем массив ai.

2) ƒл€ j=2, 3, Е, n и k=n, n-1, Е, j в первом случае поднима€сь, а во втором спуска€сь, проводим преобразование коэффициентов по следующим формулам:

а) ak-1=ak-2-ak

б) ak=2ak

¬ результате получаем коэффициенты полинома Pn(x)

II. ѕреобразование коэффициентов полинома Pn(x) в коэффициенты полинома Tn(x)

1) ¬водим коэффициенты полинома Pn(x) Ч аi

2) ƒл€ j=n, n-1, Е, 2 и k=j, j+1, Е, n †в первом случае спуска€сь, а во втором поднима€сь, проводим преобразование коэффициентов по следующим формулам:

а) ak=ak/2

б) ak-2=ak-2+ak

ñ) a0=2a0

¬ результате получим коэффициенты полинома “n(x). Ћюбопытно было бы узнать, какую ошибку мы получаем при разложении степенной функции по полиномам „ебышева. ƒл€ этого, использу€ выше описанные алгоритмы, € сначала† представл€л функцию y=xn (где n брал от 1 до 10) через полиномы „ебышева (Tn), а затем чтобы оценить ошибку чебышевское разложение снова превращал в многочлен. ¬ыполнив эти операции, € получил достаточно интересные результаты. ƒл€ нечЄтных n ошибка настолько мала, что еЄ едва можно различить на графиках (стр. ). ƒл€ чЄтных же степеней мы наблюдаем смещение графика, полученного в результате преобразовани€, вниз относительно оригинала. Ёто можно объ€снить следующим образом. «а смещение графика несЄт ответственность коэффициент перед x0. ¬спомним алгоритмы, они построены так, что каждый предыдущий коэффициент вычисл€етс€ через последующий. “о есть в результате накапливающа€с€ ошибка вычислени€ больше всего вли€ет на коэффициент при x0. —ледствием этого €вл€етс€ смещение графиков чЄтных степеней, так как в их разложении присутствует этот коэффициент. «аметим также, что смещение при разложении функции y=x2 больше, чем при разложении функции y=x10. Ётот тоже легко объ€снить, так как при увеличении степени вклад T0 в разложении степенной функции уменьшаетс€. „то же касаетс€ нечЄтных степеней, то мы получили такое хорошее совпадение так как чЄтные коэффициенты в разложении нечЄтных степеней равны 0, а коэффициенты при всех степен€х x, кроме нулевой вли€ют лишь на отклонение ветвей. ѕодтверждением этого служат графики на странице† .

—ледующим этапом работы €вл€лось приближение полиномами „ебышева произвольной функции. ¬ качестве исходной функции € вз€л функцию y=sin(4x/3). »спользуема€ в работе программа представлена на странице† . ƒл€ еЄ написани€ был использован следующий алгоритм:

I.   ѕриближение функции f(x) по „ебышеву.

1) «адаЄм степень n многочлена Tn(x) и пределы [a; b] изменени€ аргумента функции f(x).

2) ƒл€ i=0, 1, Е, n на отрезке [-1; 1] формируем сетку оптимальных значений аргумента в узлах чебышевской интерпол€ции:

††††††††††

ѕереводим †в отрезок [a; b]:

†††††††††† †и вычисл€ем f(xi)

3) ƒл€ k=0, 1, Е, n è i=0, 1, Е, n вычисл€ем:

††††††††††

¬ результате получаем коэффициенты a0, a1, Е, an многочлена T(), ïðèáëèæàþùåãî ôóíêöèþ f(x).

II. ¬ычисление значений T(x) выполн€етс€ по следующему алгоритму:

1) —чита€ заданным массив ak, задаЄм пам€ть под массив из n+2 вспомогательных коэффициентов bk. ѕолагаем bn+2=0, bn+1=0.

2) «адаЄм значени€ x на [a; b] и переводим их в отрезок [-1; 1] с помощью преобразований:

††††††††††

3) ƒл€ k=n, n-1, Е, 1 вычисл€ем bk=ak-bk+2+2xbk+1.

4) Ќаходим T()=a0/2 - b2 +xb1

“акже в программе было использовано разложение в р€д “ейлора дл€ сравнени€ с разложением по полиномам „ебышева. ѕрежде всего € рассмотрел приближение на интервале [-1; 1]. Ќаложив на график sin(4x/3) график его приближени€ полиномами „ебышева и график, построенный с помощью разложени€ в р€д “ейлора, € получил очень точное совпадение. ¬изуально нельз€ различить три кривых. –ассмотрим график ошибок. ¬ соответствии с теорией ошибка „ебышева знакопеременна и распределена более или менее равномерно по всему интервалу. ќшибка же “ейлора небольша€ около 0 и сильно увеличиваетс€ при приближении к 1 (заметим, что в этом и в других случа€х р€д “ейлора содержит те же степени x, но с другими коэффициентами). »нтереснее рассмотреть приближение на более длинных интервалах. Ќа интервале [-1; 1] приближение полиномами „ебышева 7-й степени достаточно хорошее, но уже на интервале [-10; 10] приближение этой же степенью очень плохое (стр.† ). –ассмотрим приближение на этом же интервале полиномом более высокой степени (T11). ѕолучим неплохое приближение, причЄм на графике очень чЄтко видно, что ошибка распределена равномерно. «десь оп€ть хотелось бы сравнить с разложением в р€д “ейлора. ≈сли посмотреть на графики на странице† , мы увидим, что приближение с помощью р€дов “ейлора очень хорошее в середине интервала, но сильно отклон€етс€ от эталона на концах. —равним ошибки чебышевского приближени€ и приближени€ с помощью р€дов “ейлора. ѕри этом сравнении €сно про€вл€ютс€ свойства полиномов „ебышева Ч максимальна€ ошибка меньше, чем при использовании р€да “ейлора.

»так, мы получили, что на большом интервале хорошее приближение можно построить только использу€ достаточно большие степени. ƒействительно, трудно представить себе приближение нескольких периодов синуса с помощью полиномов 3-й, 4-й, 5-й степеней и уж совсем невозможно 1-й и 2-й.

ѕолиномы „ебышева дают очень хорошее приближение функции в том смысле, что максимальна€ ошибка этого приближени€ мала, но эти приближени€ довольно сложно вычисл€ть. ќбычно относительно малое уменьшение ошибки не стоит того труда, который приходитс€ тратить на нахождение этого приближени€. ѕоэтому полиномы „ебышева используют дл€ корректировки разложени€ в р€д “ейлора. Ќахождение исправленных коэффициентов не представл€ет большой сложности, поэтому этот метод, называемый экономизацией степенного р€да может примен€тьс€ дл€ повседневного программировани€.

¬ведение ≈сли задана функци€ y(x), то это означает, что любому допустимому значению х сопоставлено значение у. Ќо нередко оказываетс€, что нахождение этого значени€ очень трудоЄмко. Ќапример, у(х) может быть определено как решение сложной задачи

 

 

 

¬нимание! ѕредставленный –еферат находитс€ в открытом доступе в сети »нтернет, и уже неоднократно сдавалс€, возможно, даже в твоем учебном заведении.
—оветуем не рисковать. ”знай, сколько стоит абсолютно уникальный –еферат по твоей теме:

Ќовости образовани€ и науки

«аказать уникальную работу

—вои сданные студенческие работы

присылайте нам на e-mail

Client@Stud-Baza.ru