درون یابی هرمیت – از صفر تا صد

در آموزش‌های قبلی مجله فرادرس، برخی از روش‌های درون‌یابی مانند چندجمله‌ای لاگرانژ و درون‌یابی اسپلاین را معرفی کردیم. در این آموزش، با روشی دیگر به نام «درون یابی هرمیت» (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}$$

فیلم آموزش محاسبات عددی با متلب MATLAB در فرادرس

کلیک کنید

مثال ۱

نتیجه درون یابی هرمیت تابع $$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$$ است.

برنامه متلب مربوط به پیاده‌سازی روش درون یابی هرمیت به صورت زیر است:

در ادامه، حالتی را در نظر می‌گیریم که $$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}$$ است.

کد متلب زیر، پیاده‌سازی این الگوریتم را نشان می‌دهد:

آرایه تفاضل‌های تقسیم شده تولیدی با تابع DividedDifference2 در جدول زیر آورده شده است که در آن، درایه‌های قطری ضرایب چندجمله‌ای هرمیت هستند.

مثال ۳

تابع $$f ( x ) = x ^ 8 + 1$$ را در نظر بگیرید. برای درون یابی هرمیت تابع و دو مشتق اول آن را در $$x \in \{-1, 0, 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) — به زبان ساده
• تقریب خطی — به زبان ساده

^^