درون یابی هرمیت — از صفر تا صد
در آموزشهای قبلی مجله فرادرس، برخی از روشهای درونیابی مانند چندجملهای لاگرانژ و درونیابی اسپلاین را معرفی کردیم. در این آموزش، با روشی دیگر به نام «درون یابی هرمیت» (Hermite Interpolation) آشنا میشویم.
روش چندجملهای درونیاب هرمیت بسیار نزدیک به چندجملهای نیوتن است، بدین صورت که در هر دوی این روشها از تفاضلهای تقسیم شده استفاده میشود. البته چندجملهای درونیاب هرمیت را میتوان بدون استفاده از تفاضلهای تقسیم شده نیز محاسبه کرد. در این صورت از «قضیه باقیمانده چینی» (Chinese Remainder Theorem) استفاده میشود.
برخلاف درونیابی نیوتن، درون یابی هرمیت یک تابع را به $$n$$ نقطه و تعداد $$m$$ مشتق آنها تطبیق میدهد. این بدین معنی است که برخلاف درونیابی نیوتن که فقط به $$ n$$ مقدار اول نیاز دارد، تعداد $$ n ( m + 1 ) $$ مقدار زیر باید معلوم باشند:
$$ \large \begin {matrix}
( x _ 0 , y _ 0 ) , & ( x _ 1 , y _ 1 ) , & \ldots , & ( x _ {n -1 } , y _ { n - 1 } ) , \\
( x _ 0 , y _ 0' ) , & ( x _ 1 , y _ 1' ) , & \ldots , & ( x _ { n - 1 } , y _ { n - 1 }' ) , \\
\vdots & \vdots & &\vdots \\
( x _ 0 , y _ 0 ^ { ( m) } ) , & ( x _ 1 , y _ 1 ^ { ( m ) } ) , & \ldots , & ( x _ { n - 1 } , y _ { n - 1 } ^ { ( m) } )
\end {matrix} $$
چندجملهای به دست آمده ممکن است از درجه حداکثر $$ n ( m + 1 ) - 1 $$ باشد، در حالی که حداکثر درجه چندجملهای نیوتن $$ n - 1 $$ است. در حالت کلی، لازم نیست $$m$$ یک مقدار ثابت باشد؛ یعنی تعدادی از نقاط ممکن است مشتقهای معلوم بیشتری نسبت به سایرین داشته باشند. در این حالت، چندجملهای منتجه ممکن است از درجه $$N- 1 $$ باشد که در آن، $$ N $$ تعداد نقاط نقاط دادهها است.
در ادامه، ابتدا یک حالت ساده را بررسی کرده، سپس درون یابی هرمیت را در حالت کلی مورد بررسی قرار میدهیم.
درون یابی هرمیت
اگر $$m$$ مشتق اول تابع $$ f ( x ) $$ و نیز خود تابع در $$n+1$$ نقطه $$ x _ 0 $$، $$ x _ 1 $$، ... و $$ x _ n $$ معلوم باشند، یعنی یک مجموعه $$ (n+1)(m+1)$$تایی از مقادیر $$ y _ j ^{(i)} = f ^{(i)} ( x _ j )$$ داشته باشیم ($$ j = 0, ... , n , i = 0 , ... , m $$)، آنگاه میتوانیم یک چندجملهای درجه $$ ( n + 1 ) ( m + 1 ) - 1 $$ را درونیابی کنیم:
$$ \large H _ { ( n + 1 ) ( m + 1 ) - 1 } ( x ) = \sum _ { k = 0 } ^ { ( n + 1 ) ( m + 1 ) - 1 } c _ { k} x ^ { k } $$
در عمل، تعداد $$ ( n + 1) ( m + 1 ) $$ ضریبِ $$ c _ 0 $$، $$c_ 1$$، ... و $$ c _{(n+1)(m+1) - 1}$$ را میتوان برای حل یک دستگاه معادله خطی از تعداد مشابهی معادله به دست آورد:
$$ \large \begin {align*}
\left . \frac { d ^ { i } } { d x ^ { i } } H ( x ) \right | _ { x = x _ { j } } & =\left . \frac { d ^ { i } } { d x ^ { i } } \left ( \sum _ { k = 0 } ^ { ( n + 1 ) ( m + 1 ) - 1 } c _ { k } x ^ { k } \right ) \right | _ { x = x _ { j } } \\ & = f ^{ ( i ) } \left ( x _ { j } \right ) , \quad ( j = 0 , \cdots , n , i = 0 , \cdots , m ) \end {align*} $$
ضرایب و جواب این دستگاه معادلات یکتا هستند. البته، این روش به دلیل پیچیدگی بالای محاسباتی $$ O ( ( m n )^ 3 ) $$ غیرعملی است.
در عمل، در این حالت، از درون یابی هرمیت میتوان استفاده کرد. ابتدا فرض میکنیم $$ m = 1 $$ است و چندجملهای هرمیت را به عنوان یک ترکیب خطی از $$ ( n + 1 ) ( m + 1 ) = 2 ( n + 1 ) $$ چندجملهای اساسی یا پایه $$ \alpha _ i ( x )$$ و $$ \beta _ i ( x ) $$ از درجه $$ 2 n + 1 $$ نمایش میدهیم که در آن، $$ i = 0 , ... , n $$ است:
$$ \large H ( x ) = \sum _ { i = 0 } ^ { n } \alpha _ { i } ( x ) f \left ( x _ { i } \right ) + \sum _ { i = 0 } ^ { n } \beta _ { i } ( x ) f ^ { \prime } \left ( x _ { i } \right ) $$
برای آنکه $$ H ( x ) $$ در $$ H ( x _ j ) = f ( x _ j ) $$ و $$ H' ( x _ j ) = f' ( x _ j ) $$ برای $$ j = 0 , ... , n $$ صدق کند، چندجملهایهای پایه باید در روابط زیر صدق کنند:
$$ \large \alpha _ i ( x _ j ) = \beta _ i^ \prime ( x _ j ) = \delta _ { i j } ,\; \;\;\; \alpha _ i ^ \prime ( x _ j ) = \beta _ i ( x _ j ) = 0 , \;\;\; \; ( i , j = 0 , ... , n ) $$
از آنجا که چندجملهای مرتبه $$n$$اُم لاگرانژ $$ l _ i (x) $$ در $$ l _ i ( x _ j ) = \delta _ { i j } $$ صدق میکند، چندجملهایهای پایه را از مرتبه $$ 2 n + 1 $$ قرار میدهیم و خواهیم داشت:
$$ \large \alpha _ i ( x ) = ( a x + b ) l _ i ^ 2 ( x ) , \;\;\;\; \beta _ i ( x ) = ( c x + d ) l _ i ^ 2 , \;\;\;\; ( i = 0 , ..., n ) $$
اکنون باید پارامترهای $$ a $$، $$ b $$، $$ c $$ و $$ d $$ را برای آنکه $$ \alpha _ i ( x ) $$ و $$ \beta _ i ( x ) $$ در $$ x = x _ i $$ برقرار باشند به دست آوریم:
$$ \large \begin {array} {l}
{ \left \{ \begin {array} { l }
{ \alpha _ { i } \left ( x _ { i } \right ) = \left ( a x _ { i } + b \right ) l _ { i } ^ { 2 } \left ( x _ { i } \right ) = a x _ { i } + b = 1 } \\
{ \alpha _ { i } ^ { \prime } \left ( x _ { i } \right ) = a l _ { i } ^ { 2 } \left ( x _ { i } \right ) + \left ( a x _ { i } + b \right ) 2 l _ { i } ^ { \prime } \left ( x _ { i } \right ) = a + 2 l _ { i } ^ { \prime } \left ( x _ { i } \right ) = 0 } \\
\end {array} \right . }
\end {array} $$
$$ \large \begin {array} {l}
{ \left \{ \begin {array} { l }
{ \beta _ { i } \left ( x _ { i } \right ) = \left ( c x _ { i } + d \right ) l _ { i } ^ { 2 } \left ( x _ { i } \right ) = c x _ { i } + d = 0 } \\
{ \beta _ { i } ^ { \prime } \left ( x _ { i } \right ) = c l _ { i } ^ { 2 } \left ( x _ { i } \right ) + \left ( c x _ { i } + d \right ) 2 l _ { i } ^ { \prime } \left ( x _ { i } \right ) = c = 1 } \end {array} \right . }
\end {array} $$
با حل دو جفت معادله بالا، داریم:
$$ \large \begin {array} {l}
{ \left \{ \begin {array} { l }
a = - 2 l _ i ^ \prime ( x _ i ) \\
b = 1 + 2 x _ i l _ i ^ \prime ( x _ i )
\end {array} \right . }
\end {array} \; , \;\;\; \;\;
\large \begin {array} {l}
{ \left \{ \begin {array} { l }
c = 1 \\
d = - x _ i
\end {array} \right . }
\end {array} $$
و
$$ \large \left \{ \begin {array} { l }
{ \alpha _ { i } ( x ) = ( a x + b ) l _ { i } ^ { 2 }( x ) = \left ( 1 - 2 l _{ i } ^ { \prime } ( x ) \left ( x -x _ { i } \right ) \right ) l _ { i } ^ { 2 } ( x ) } \\
{ \beta _ { i } ( x ) = ( c x + d ) l _ { i } ^ { 2 } ( x ) = \left ( x - x _ { i } \right ) l _ { i } ^ { 2 } ( x ) }
\end {array} \right . $$
اکنون چندجملهای درونیاب هرمیت را میتوان به صورت زیر نوشت:
$$ \large \begin {aligned}
H ( x ) & = \sum _ { i = 0 } ^ { n } \alpha _ { i } ( x ) f \left ( x _ { i } \right ) + \sum _ { i = 0 } ^ { 2 } \beta _ { i } ( x ) f ^ { \prime } \left ( x _ { i } \right ) \\
& = \sum _ { i = 0 } ^ { n } \left ( 1 - 2 l _ { i } ^ { \prime } ( x ) \left ( x - x _ { i } \right ) \right ) l _ {i } ^ { 2 } ( x ) f \left ( x _ { i } \right ) + \sum _ { i = 0 } ^ { n } \left ( x - x _ { i } \right ) l _ { i } ^ { 2 } ( x ) f ^ { \prime } \left ( x _ { i } \right ) \\
& = \sum _ { i = 0 } ^ { n } \left [ f \left ( x _ { i } \right ) + \left ( x - x _ { i } \right ) \left ( f ^ { \prime } \left ( x _ { i } \right ) - 2 f \left ( x _ { i } \right ) l _ { i } ^ { \prime }( x ) \right ) \right ] l _ { i } ^ { 2 } ( x )
\end {aligned} $$
مثال ۱
نتیجه درون یابی هرمیت تابع $$ y = f ( x ) = x \sin ( 2 x + \pi / 4 ) + 1 $$ در شکل زیر نشان داده شده است. همچنین، چندجملهایهای $$ \alpha _ i ( x ) $$ و $$ \beta _ i ( x ) $$ برای $$ i = 0 , ... , 3 $$ رسم شدهاند. از آنجا که مشتق اول $$ f' ( x _ i ) $$ و مقدار تابع $$ f ( x _ i ) $$ در هر نقطه $$ x _ i $$ در دسترس هستند، میانیابی $$ H ( x ) $$ با تابع داده شده $$ f ( x ) $$ بسیار منطبق بوده (در شکل منطبق و یکسان هستند) و خطا $$ \epsilon = 0.0040 $$ است.
برنامه متلب مربوط به پیادهسازی روش درون یابی هرمیت به صورت زیر است:
1function [H a b]=HIL(u,x,y,dy) % Hermite interpolation (Lagrange)
2 % u: discrete data points;
3 % vector x: [x_1,...,x_n]
4 % vector y: [y_1,...,y_n]
5 % vector dy: [y'_1,...,y'_n]
6 n=length(x); % number of interpolating points
7 k=length(u); % number of discrete data points
8 li=ones(n,k); % Lagrange basis polynomials
9 a=zeros(n,k); % basis polynomials alpha(x)
10 b=zeros(n,k); % basis polynomials beta(x)
11 H=zeros(1,k); % Hermie interpolation polynomial H(x)
12 for i=1:n
13 dl=0; % derivative of Lagrange basis
14 for j=1:n
15 if j~=i
16 dl=dl+1/(x(i)-x(j));
17 li(i,:)=li(i,:).*(u-x(j))/(x(i)-x(j));
18 end
19 end
20 l2=li(i,:).^2;
21 b(i,:)=(u-x(i)).*l2; % basis polynomial alpha(x)
22 a(i,:)=(1-2*(u-x(i))*dl).*l2; % basis polynomial beta(x)
23 H=H+a(i,:)*y(i)+b(i,:)*dy(i); % Hermite polynomial H(x)
24 end
25end
در ادامه، حالتی را در نظر میگیریم که $$ m > 1 $$ باشد. اکنون $$ m + 1 $$ متغیر معلوم $$ f ( x _ i )$$، $$ f' ( x _ i )$$، ... و $$ f ^ {(m)} ( x _ i ) $$ در هر یک از نقاط $$x _ 0 $$، ... و $$ x _ n$$ معلوم هستند. مطابق جدول زیر، مجموعه داده متغیر دیگر $$ z $$ را که شامل $$ x _ 0 $$، ... و $$ x _ n $$ در هر $$m$$ تکرار است، تعریف میکنیم:
با روش چندجملهای نیوتن میتوان تابع $$ f ( z ) $$ را با $$ ( n + 1 ) ( m + 1 ) $$ نقطه نمونه درونیابی کرد. برای مثال، اگر $$ m = n = 2$$ باشد، آنگاه چندجملهای درجه $$ ( 2 + 1 ) ( 2 + 1 ) - 1 = 8 $$ را میتوان به صورت زیر به دست آورد:
$$ \large \begin {aligned}
N _ { 8 } ( x ) = & f \left ( z _ { 0 } \right ) + \sum _ { i = 1 } ^ { 8 } f \left [ x _ { 0 } , \cdots , x _ { i } \right ] \prod _ { j = 0 } ^ { i - 1 } \left ( x - x _ { j } \right ) \\
= & f \left ( z _ { 0 } \right ) + f \left [ z _ { 0 } , z _ { 1 } \right ] \left ( x - z _ { 0 } \right ) + f \left [ z _ { 0 } , z _ { 1 } , z _ { 2 } \right ] \left ( x - z _ { 0 } \right ) \left ( x - z _ { 1 } \right ) \\
& + f \left [ z _ { 0 } , \cdots , z _ { 3 } \right ] \left ( x -z _ { 0 } \right ) \left ( x - z _ { 1 } \right ) \left ( x - z _ { 2 } \right ) \\
& + f \left [ z _ { 0 } , \cdots , z _ { 4 } \right ] \left ( x - z _ { 0 } \right ) \left ( x - z _ { 1 } \right ) \left ( x - z _ { 2 } \right ) \left ( x - z _ { 3 } \right ) \\
& + f \left [ z _ { 0 } , \cdots , z _ { 5 } \right ] \left ( x -z _ { 0 } \right ) \left ( x - z _ { 1 } \right ) \left ( x - z _ { 2 } \right ) \left ( x - z _ { 3 } \right ) \left ( x - z _ { 4 } \right ) \\
& + f \left [ z _ { 0 } , \cdots , z _ { 6 } \right ] \left ( x - z _ { 0 } \right ) \left ( x - z _ { 1 } \right ) \left ( x - z _ { 2 } \right ) \left ( x - z _ { 3 } \right ) \left ( x - z _ { 4 } \right ) \left ( x -z _ { 5 } \right ) \\
& + f \left [ z _ { 0 } , \cdots , z _ { 7 } \right ] \left ( x -z _ { 0 } \right ) \left ( x - z _ { 1 } \right ) \left ( x - z _ { 2 } \right ) \left ( x - z _ { 3 } \right ) \left ( x - z _ { 4 } \right ) \left ( x - z _ { 5 } \right ) \left ( x - z _ { 6 } \right ) \\
& + f \left [ z _ { 0 } , \cdots , z _ { 8 } \right ] \left ( x - z _ { 0 } \right ) \left ( x - z _ { 1 } \right ) \left ( x -z _ { 2 } \right ) \left ( x - z _ { 3 } \right ) \left ( x - z _ { 4 } \right ) \left ( x - z _ { 5 } \right ) \left ( x - z _ { 6 } \right ) \left ( x - z _ { 7 } \right ) \\
= & f \left ( x _ { 0 } \right ) + f \left [ x _ { 0 } , x _ { 0 } \right ] \left ( x - x _ { 0 } \right ) + f \left [ x _ { 0 } , x _ { 0 } , x _ { 0 } \right ] \left ( x - x _ { 0 } \right ) ^ { 2 } + f \left [ x _ { 0 } , x _ { 0 } , x _ { 0 } , x _ { 1 } \right ] \left ( x - x _ { 0 } \right ) ^ { 3 } \\
& + f \left [ x _ { 0 } , x _ { 0 } , x _ { 0 } , x _ { 1 } , x _ { 1 } \right ] \left ( x - x _ { 0 } \right ) ^ { 3 } \left ( x - x _ { 1 } \right ) + f \left [ x _ { 0 } , x _ { 0 } , x _ { 0 } , x _ { 1 } , x _ { 1} , x _ { 1 } \right ] \left ( x - x _ { 0 } \right ) ^ { 3 } \left ( x - x _ { 1 } \right ) ^ { 2 } \\
& + f \left [ x _ { 0 } , x _ { 0 } , x _ { 0 } , x _ { 1 } , x _ { 1 } , x _ { 1 } , x _ { 2 } \right]\left ( x -x _ { 0 } \right ) ^ { 3 } \left ( x - x _ { 1 } \right ) ^ { 3 } \\
& + f \left [ x _ { 0 } , x _ { 0 } , x _ { 0 } , x _ { 1 } , x _ { 1 } , x _ { 1 } , x _ { 2 }, x _ { 2 } \right ] \left ( x -x _ { 0 } \right ) ^ { 3 } \left ( x - x _ { 1 } \right ) ^ { 3 } \left ( x -x _ { 2 } \right ) \\
& + f \left [ x _ { 0 } , x _ { 0 } , x _ {0 } , x _ { 1 } , x _ { 1 } , x _ { 1 } , x _ { 2 } , x _ { 2 } , x _ { 2 } \right] \left ( x - x _ { 0 } \right ) ^ { 3 } \left ( x - x _ { 1 } \right ) ^ { 3 } \left ( x - x _ { 2 } \right ) ^ { 2 }
\end {aligned} $$
میتوان تأیید کرد که در واقع، $$ N _ 8 ^ { ( i ) } ( x _ j ) = f ^ { ( i )} ( x _ j ) $$ برای همه $$ i = 1 , ... , m $$ و $$ j = 0 , ... , n $$ برقرار است. مشابه روش چندجملهای نیوتن، ضرایب تفاضلهای تقسیم شده را میتوان به صورت بازگشتی به دست آورد (تنها با این تفاوت که $$m + 1 $$ تکرار در هر نقطه $$ x _ i $$ وجود دارد). تفاضل تقسیم شده به صورت زیر به دست میآید:
$$ \large f \left [ x _ { 0 } , \cdots , x _ { 0 } \right ] = \lim _ { x _ { i } \rightarrow x _ { 0 } , ( i = 0 , \cdots , n ) } f \left [ x _ { 0 } , \cdots , x _ { n } \right ] = \frac { f ^ { ( n ) } \left ( x _ { 0 } \right ) } { n ! } $$
ضرایب تفاضل تقسیم شده در عبارت $$ N _ 8 ( x ) $$ بالا را میتوان به صورت بازگشتی در جدول زیر تولید کرد. این ضرایب، به عنوان عناصر قطری جدول نمایان میشوند.
مثال ۲
اکنون درون یابی هرمیت را برای تابع $$ y = f ( x ) = x \sin ( 2 x + \pi / 4 ) + 1 $$ انجام میدهیم. فرض میکنیم هر دو مشتق $$ f' ( x _ i ) $$ و $$ f^{\prime \prime} ( x _ i ) $$ و نیز $$ f ( x _ i ) $$ در چهار نقطه در دسترس باشند. درون یابی هرمیت $$ H( x) $$ همراه با تابع $$ f ( x) $$ در شکل زیر رسم شدهاند. همانطور که میبینیم، این دو بسیار شبیه هستند و خطای آنها $$ \epsilon = 6.5 \times 10 ^ {-6} $$ است.
کد متلب زیر، پیادهسازی این الگوریتم را نشان میدهد:
1function [v]=HIN(u,x,dy) % Hermite interpolation (Newton)
2 % u: discrete data points;
3 % vector x: [x_1,...,x_n]
4 % matrix dy contains m derivatives at each of the n points
5 [n m]=size(dy);
6 k=length(u); % number of discrete data points
7 v=zeros(1,k); % interpolation results
8 dd=DividedDifference2(x,dy); % get the divided difference array
9 w=ones(1,k);
10 for i=1:n
11 p=u-x(i);
12 for j=1:m
13 l=(i-1)*m+j; % index of the coefficient
14 v=v+dd(l,l).*w; % which is on the diagnal of array dd
15 w=w.*p;
16 end
17 end
18end
19
20function dd=DividedDifference2(x,dy) % generate array of divided differences
21 [n m]=size(dy); % n data points, m derivatives (0 to m-1)
22 dd=zeros(n*m); % matrix of divided differences
23 z=zeros(1,n*m);
24 k=1;
25 for i=1:n % n data points
26 for j=1:m % m derivatives (0 to m-1) at each point
27 k=(i-1)*m+j; % row index
28 z(k)=x(i);
29 dd(k,1)=dy(i,1); % 0th divided difference in first column
30 fprintf('%6.3f\t%6.3f\t',z(k),dd(k,1));
31 for l=2:k % column index for the remaining columns
32 %fprintf('(%f %f)\n',dd(k,l-1),dd(k-1,l-1));
33 if dd(k,l-1)==dd(k-1,l-1) % left and top-left neighbors are repeated
34 dd(k,l)=dy(i,l)/factorial(l-1);
35 fprintf('k=%d, l=%d\n',k,l);
36 pause
37 else
38 dd(k,l)=(dd(k,l-1)-dd(k-1,l-1))/(z(k)-z(k-l+1));
39 end
40 fprintf('%6.3f\t',dd(k,l));
41 end
42 fprintf('\n');
43 end
44 end
45end
آرایه تفاضلهای تقسیم شده تولیدی با تابع DividedDifference2 در جدول زیر آورده شده است که در آن، درایههای قطری ضرایب چندجملهای هرمیت هستند.
مثال ۳
تابع $$ f ( x ) = x ^ 8 + 1 $$ را در نظر بگیرید. برای درون یابی هرمیت تابع و دو مشتق اول آن را در $$ x \in \{-1, 0, 1\} $$ محاسبه کرده و دادههای زیر را به دست میآوریم:
$$ f^{\prime \prime} ( x ) $$ | $$f' ( x ) $$ | $$ f ( x ) $$ | $$ x $$ |
$$ 56 $$ | $$ - 8 $$ | $$ 2 $$ | $$ -1$$ |
$$ 0$$ | $$ 0 $$ | $$ 1 $$ | $$ 0 $$ |
$$ 56$$ | $$ 8$$ | $$ 2 $$ | $$ 1 $$ |
از آنجا که با دو مشتق سر و کار داریم، مجموعه $$ \{ z _ i \} = \{ - 1 , - 1 , - 1 , 0 , 0 , 0 , 1 , 1 , 1 \} $$ را تشکیل میدهیم. جدول تفاضل تقسیم شده نیز به صورت زیر خواهد بود:
و چندجملهای تولید شده برابر است با:
$$ \large \begin {align}
P ( x ) & = 2 - 8 ( x + 1 ) + 2 8 ( x + 1 ) ^ 2 - 2 1 ( x + 1 ) ^ 3 + 1 5 x ( x + 1 ) ^ 3 - 1 0 x ^ 2 ( x + 1 ) ^ 3 \\
& \quad {} + 4 x ^ 3 ( x + 1 ) ^ 3 - 1 x ^ 3 ( x + 1 ) ^ 3 ( x - 1 ) + x ^ 3 ( x + 1 ) ^ 3 ( x - 1 ) ^ 2 \\
& = 2 - 8 + 2 8 - 2 1 - 8 x + 5 6 x - 6 3 x + 1 5 x + 2 8 x ^ 2 - 6 3 x ^ 2 + 4 5 x ^ 2 - 1 0 x ^ 2 - 2 1 x ^ 3 \\
&\quad {} + 4 5 x ^ 3 - 3 0 x ^ 3 + 4 x ^ 3 + x ^ 3 + x ^ 3 + 1 5 x ^ 4 - 3 0 x ^ 4 + 1 2 x ^ 4 + 2 x ^ 4 + x ^ 4 \\
& \quad {} - 1 0 x ^ 5 + 1 2 x ^ 5 - 2 x ^ 5 + 4 x ^ 5 - 2 x ^ 5 - 2 x ^ 5 - x ^ 6 + x ^ 6 - x ^ 7 + x ^ 7 + x ^ 8 \\
& = x ^ 8 + 1 . \end {align} $$
با گرفتن ضرایب از قطر جدول تفاضل تقسیم شده و ضرب $$k$$اُمین ضریب در $$ \prod _ { i = 0 } ^ { k - 1 } ( x - z _ i) $$، جواب مورد نظر به دست میآید.
خطای درون یابی هرمیت
اگر چندجملهای محاسبه شده از درون یابی هرمیت را $$H$$ و تابع اصلی را $$ f $$ بنامیم، تابع خطا برای $$ x \in [x_0, x_n] $$ به صورت زیر است:
$$ \large f ( x ) - H ( x ) = \frac { f ^ { ( K ) } ( c ) } { K ! } \prod _ { i } ( x - x _ i ) ^ { k _ i } $$
که در آن، $$ c $$ یک مجهول در بازه $$ [ x _ 0 , x _ N] $$، پارامتر $$k$$ تعداد کل نقطه-دادهها و $$ k _ i $$ تعداد مشتقهای معلوم در هر $$ c _ i $$ به علاوه یک است.
اگر این مطلب برایتان مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای محاسبات عددی
- آموزش محاسبات عددی (مرور و حل مساله)
- مجموعه آموزشهای دروس ریاضیات
- آموزش محاسبات عددی با MATLAB
- روش ژاکوبی — به زبان ساده
- برازش منحنی (Curve Fitting) — به زبان ساده
- تقریب خطی — به زبان ساده
^^
سلام ی سوال داشتم
چطور میتونیم ثابت کنیم که تعداد محاسبات درونیابی fft،
nlogn است؟