قضیه ۲

فرض کنید $$f: Z^+rightarrow Z^+$$

$$sum_{j=0}^{infty} a_j= sum_{j=0}^{infty} a_{f(j)}$$

قضیه ۳

انجام عملیات زیر روی سری‌های مطلقا همگرا درست است:

• عبور قدر مطلق‌ از بیرون جمع به داخل:

$$| sum_{j=0}^{infty} a_j| leq sum_{j=0}^{infty} |a_j|$$

• مبادله جمع‌ها:

$$sum_{j=0}^{infty} sum_{k=0}^{infty} a_{j,k} = sum_{k=0}^{infty} sum_{j=0}^{infty} a_{j,k}$$

نماد O بزرگ

پس از اینکه تا حدی یاد گرفتیم مفهوم همگرایی سری‌ها در محاسبات عددی چیست، در این بخش می‌خواهیم چند نماد معمول برای مقایسه رشد یا کاهش دنباله‌ها معرفی کنیم. سه نماد معروف در این زمینه داریم که عبارت‌اند از:

• نماد $$O$$ بزرگ
• نماد $$o$$ کوچک
• نماد $$ominus$$ بزرگ

1. اگر $$C$$ بزرگتر از صفر و مثبتی وجود داشته باشد به گونه‌ای که $$|f_n| leq C|g_n|$$
2. اگر همزمان با $$n rightarrow infty$$
3. اگر $$f_n=O(g_n)$$

• به ازای هر $$a$$ و $$b$$ مثبتی: $$n^a = o (e^{bn})$$
• به ازای هر $$a$$ و $$b$$ مثبتی: $$e^{-bn} = o (n^{-a})$$

برای اینکه قوانین بالا را بهتر متوجه شوید، به مثال‌های زیر توجه کنید.

مثال ۱

فرض کنید $$f_n=n^2$$

پاسخ

در اولین مورد باید یک $$C$$ بزرگتر از صفر و مثبتی وجود داشته باشد به‌طوری که $$|f_n| leq C|g_n|$$

$$|n^2| leq C|n^3| Rightarrow 1 leq C|n| Rightarrow1 leq1$$

و برای $$n=2$$

$$|n^2| leq C|n^3| Rightarrow 1 leq C|n| Rightarrow1 leq2$$

به این ترتیب درستی $$|f_n| leq C|(g_n)|$$

$$frac{f_n}{g_n} = frac{n^2}{n^3} =frac{1}{n}$$

بنابراین اگر $$n rightarrow infty$$

مثال ۲

درستی $$f_n=O(g_n)$$

پاسخ

طبق تعریف برای برقراری $$f_n=O(g_n)$$

$$|frac{n}{n+2}| leq C |frac{n}{n-3}|$$

چون لازم است دنباله‌های $$f_n$$

$$frac{2}{6} leq C frac{3}{6} Rightarrow frac{2}{6} leq frac{3}{6}$$

پس درستی $$|f_n| leq C|g_n|$$

$$frac{f_n}{g_n} = frac{frac{n}{n+2}}{frac{n}{n-3}} = frac{n-3}{n+2}$$

$$lim_{n rightarrow infty} frac{n-3}{n+2} = frac{-3}{2} neq 0$$

در نتیجه دومین مورد برای این دو دنباله صحیح نیست و داریم $$f_n neq o(g_n)$$

$$|frac{n}{n-3}| leq C |frac{n}{n+2}| Rightarrow |frac{1}{1-3}| leq |frac{2}{3}| Rightarrow frac{3}{6} leq frac{4}{6}$$

پس چون توانستیم یک $$C$$ بزرگتر از صفر و مثبتی پیدا کنیم که نامساوی بالا به ازای آن درست باشد، بنابراین داریم $$g_n=O(f_n)$$

بسط تیلور چیست؟

اگر بتوانیم تابع $$f(x)$$ را حول نقطه‌ای مانند $$x=a$$

$$f(x) = f(a) + f^{‘}(a) (x-a) + frac{1}{2} f^{”}(a) (x-a)^2 + frac{1}{3!} f^{”’}(a) (x-a)^3 + …$$

در این صورت عبارت بالا بسط تیلور تابع $$f(x)$$ نامیده می‌شود و فرم فشرده‌تر آن در قالب سری تیلور به شکل زیر خواهد شد:

$$f(x) = sum_{n=0}^{infty} frac{1}{n!}f^{(n)}(a) (x-a)^n$$

$$|x-a| < R$$

این امکان در مورد سری تیلور با $$N$$ جمله وجود دارد که آن را در قالب دو جمله و به شکل زیر بازنویسی کنیم:

$$f(x) = sum_{n=0}^{N-1} frac{1}{n!}f^{(n)}(a) (x-a)^n +frac{1}{N!}f^{(N)}(y) (x-a)^N$$

با این شرط که $$y$$ عددی بین $$x$$ و $$a$$ است. دقت کنید این فرمول مشخص نمی‌کند مقدار دقیق عدد $$y$$ چیست، بلکه فقط بیان می‌کند عددی مانند $$y$$ به‌عنوان آخرین جمله یا باقی‌مانده در بسط بالا وجود دارد. علی‌رغم اینکه $$y$$ در عبارت بالا مشخص نیست، این شکل از نوشتن بسط تیلور بسیار کاربردی‌تر از نوشتن آن به‌صورت یک سری بی‌نهایت است. در ادامه دو جمع‌بندی مهم برای بسط تیلور و با کمک گرفتن از آنچه در اولین بخش از مطلب محاسبات عددی آموختیم، بیان می‌کنیم.

نکته ۱: از آنجا که اغلب اندازه باقی‌مانده برای ما مهم است، می‌توانیم از نامساوی زیر استفاده کنیم:

$$|frac{1}{N!}f^{(N)}(y) (x-a)^N| leq frac{1}{N!} (max _{zin [x,a]} f^{(N)}(z) ) (x-a)^N$$

یا به صورت ساده‌تر:

$$frac{1}{N!}f^{(N)}(y) (x-a)^N =O ( |x-a|^N)$$

که در آن تمام ثوابت در نماد $$O$$ بزرگ مخفی شده‌اند. بنابراین می‌توانیم بگوییم باقی‌مانده از مرتبه $$|x-a|^N$$

نکته ۲: فرمول $$N$$ متناهی زمانی معتبر است که تابع ما $$N$$ مرتبه مشتق‌پذیر باشد و این به آن معنا نیست که بی‌نهایت مرتبه مشتق‌پذیری داشته باشیم. در حقیقت، سری تیلور با اینکه ممکن است واگرا شود، اما رابطه زیر همچنان معتبر است:

$$f(x) = sum_{n=0}^{N-1} frac{1}{n!}f^{(n)}(a) (x-a)^n +frac{1}{N!}f^{(N)}(y) (x-a)^N$$

حل مثال از دنباله ها و سری ها

در ادامه چند مثال راجع‌به تعاریف و قضایای بیان شده در بخش همگرایی دنباله‌ها و سری‌ها را با هم بررسی می‌کنیم تا بهتر متوجه شوید معنای همگرایی در محاسبات عددی چیست.

مثال ۱

ثابت کنید سری $$sum_{j=0}^{infty} 2^{-j}$$

پاسخ

برای اثبات این سوال، ابتدا مجموع جزئی زیر را در نظر می‌گیریم:

$$S_N= sum_{j=0}^{infty} 2^{-j}$$

حال اجازه دهید با استقرا نشان دهیم که $$S_N= 2 – 2^{-N}$$

$$2^{-0}= 2 – 2^{-0}=1$$

پس با توجه به استقرا می‌توانیم $$S_N$$

$$S_{N+1} = S_N+2^{-(N+1)} = (2 – 2^{-N}) + 2^{-(N+1)}$$

مثال ۲

سری هارمونیک را به شکل زیر را در نظر بگیرید و واگرایی آن را نشان دهید:

$$1+frac{1}{2}+frac{1}{3}+frac{1}{4}+…$$

پاسخ

برای اثبات واگرایی این سری، کافی است نشان دهیم $$N$$ مجموع جزئی با $$log{N}$$ قابل مقایسه است. ابتدا انتگرال آزمون زیر را بکار می‌بریم:

$$S_N= sum_{j=1}^N frac{1}{j}geq int_{1}^{N+1} frac{1}{x}dx$$

انتگرال بعدی $$log{(N+1)}$$

مثال ۳

با فرض عبارت زیر برای تمام $$q$$های بزرگتر از صفر، اگر این رابطه را به عنوان تابعی از $$q$$ «تابع زتای ریمان» بنامیم و به‌صورت $$zeta (q)$$ نشان دهیم، نشان دهید این تابع که یکی از توابع موردعلاقه نظریه‌پردازان محاسبات عددی نیز به شمار می‌رود، برای مقادیر بیشتر از $$q=1$$

$$sum_{j=1}^{infty} frac{1}{n^q}$$

پاسخ

مشابه سوال قبل با بکارگیری انتگرال آزمونی مانند مثال ۲، می‌توانیم نشان دهیم که سری برای مقادیر $$q$$ بزرگتر از یک همگرا می‌شود، در حالی که برای $$q leq 1$$

مثال ۴

یک سری به شکل $$1-frac{1}{2}+frac{1}{3}-frac{1}{4}+frac{1}{5}-frac{1}{6}+…$$

پاسخ

خیر، این سری همگرایی مطلق ندارد، چون اگر مقادیر مطلق را از جملات آن حذف کنیم، به یک سری هارمونیک خواهیم رسید. بنابراین با اینکه این سری همگرای مطلق نیست، اما همگرایی مشروط دارد. فرض کنید $$N$$ زوج است و جملات سری $$S_N=sum_{j=1}^{N} frac{(-1)^j}{j}$$

$$frac{1}{j} -frac{1}{j+1} = frac{1}{j(j+1)}$$

طبق نامساوی $$frac{1}{j(j+1)} leq frac{1}{j^2}$$

$$S_N leq sum_{j=1,3,5,…}^{N-1} frac{1}{j^2}$$

که می‌دانیم این سری همگرا است. از طرفی اگر $$N$$ فرد باشد، در این صورت $$S_N=S_{N-1}+frac{1}{N+1}$$

مثال ۵

مجددا سری $$frac{1}{3}-frac{1}{4}+frac{1}{5}-frac{1}{6}+…$$

پاسخ

می‌توانیم این سری را به شکل دیگری مجددا مرتب کنیم، به این صورت که به ازای هر جمله مثبت، بلافاصله دو جمله منفی بعد از آن قرار دهیم:

$$frac{1}{3}-frac{1}{4}-frac{1}{6}+frac{1}{5}-frac{1}{8}-frac{1}{10}+…$$

این سری هم همگرا است. اما همگرایی آن برابر است با $$frac{(log 2- 1)}{2}= -0.153426…$$

روش‌ های انتگرال‌ گیری عددی

پس از اینکه در اولین بخش یاد گرفتید مفهوم دنباله و سری در محاسبات عددی چیست، دومین بخش با توضیح ساده‌ترین روش‌های انتگرال‌گیری عددی شروع می‌شود. در این بخش یاد می‌گیریم روش‌های انتگرال‌گیری عددی در محاسبات عددی چیست و هر کدام بر مبنای چه نوع تقریبی پاسخ یک انتگرال را برای ما محاسبه می‌کنند.

به همین منظور ابتدا لازم است نحوه محاسبه انتگرال‌های عددی را به کمک تقریب مرتبه اولی به نام روش مستطیلی شرح دهیم. همچنین در بخش‌های بعد روش‌های دقیق‌تری مانند روش نقطه میانی و روش ذوزنقه‌ای را معرفی می‌کنیم که هر دو از تقریب‌های مرتبه دوم برای محاسبه انتگرال استفاده می‌کنند. در تمام این مباحث هدف ما تعیین پاسخ یک انتگرال معین با روش‌های تقریبی است. در نهایت با معرفی روش سیمپسون این بخش را به پایان می‌رسانیم.

روش مستطیلی

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

با اینکه این روش بسیار ساده بنظر می‌رسد، اما پاسخ دقیق‌تر آن با در نظر گرفتن تعداد زیادی مستطیل حاصل می‌شود. برای شروع، تابعی مانند $$f$$ را در نظر بگیرید که انتگرال آن به شکل زیر محاسبه می‌شود:

$$int_{0}^{1} f (x) dx$$

اگر محدوده انتگرال‌گیری در این انتگرال را به‌صورت $$[a,b]$$ فرض کنیم و آن را به بازه‌های کوچکتری به شکل $$[x_{j-1},x_j]$$

$$x_j=jh$$

$$h = frac{1}{N}$$

$$0 = x_0 < x_1 < … < x_N = 1$$

در این صورت با در نظر گرفتن اینکه $$x_j$$

$$int_{0}^{1} f (x) dx = sum_{j=1}^N int_{x_j-1}^{x_j} f (x) dx$$

اگر انتگرال‌ها را با مقادیری که فقط به نمونه‌های $$f(x_j)$$

$$int_{x_j-1}^{x_j} f (x) dx simeq h f(x_{j-1})$$

در حقیقت در محاسبه بالا روش مستطیلی را برای محاسبه انتگرال عددی انتخاب کرده‌ایم:

$$int_{0}^{1} f (x) dx simeq sum_{j=1}^N f(x_{j-1})$$

برای اینکه دقت این تقریب را بهتر متوجه شویم، نیاز داریم از بسط تیلور استفاده کنیم که در بخش قبل آن را معرفی کردیم. تابع $$f$$ را در $$int_{x_{j-1}}^{x_j} f (x) dx$$

$$f(x) =f(x_{j-1})+ f^{‘}(y(x)) h$$

که در آن $$y(x) in [x_{j-1},x]$$

$$int_{x_{j-1}}^{x_j} f(x) dx = hf(x_{j-1}) + h int_{x_{j-1}}^{x_j}f^{‘}(y(x)) dx$$

ما در مورد تابع $$y (x)$$ چیز زیادی نمی‌دانیم اما می‌توانیم با اطمینان نامساوی زیر را برای آن بنویسیم:

$$h |int_{x_{j-1}}^{x_j}f^{‘}(y(x)) dx | leq h max _{yin [x_{j-1},x_j]} |f^{‘}(y) | int_{x_{j-1}}^{x_j} 1dx$$

با توجه به اینکه طرف دوم نامساوی بالا با عبارت زیر برابر می‌شود:

$$h max _{yin [x_{j-1},x_j]} |f^{‘}(y) | int_{x_{j-1}}^{x_j} 1dx = h^2 max _{yin [x_{j-1},x_j]} |f^{‘}(y) |$$

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

$$int_{x_{j-1}}^{x_j} f(x) dx = hf(x_{j-1}) + O (h^2)$$

که تمام مشتق‌های تابع $$f$$ در نماد $$O$$ مخفی شده‌اند. پس انتگرال در بازه $$[0,1]$$ دارای $$N$$ عدد از چنین جملاتی است و وقتی که این جملات با هم جمع می‌شوند، مقادیر خطا به شکل $$N. O (h^2) = O(h)$$

$$int_{0}^{1} f(x) dx simeq h sum_{j=1}^N f(x_{j-1}) + O (h)$$

مرتبه خطا در این بررسی با خود فاصله شبکه کارتزین یا $$h$$ برابر شد. به همین دلیل می‌گوییم این روش مرتبه اول است (چون توان $$h$$ برابر با $$1$$ است). اما اینکه طول هر مستطیل را از آخرین نقطه باقی‌مانده یعنی $$x_{j-1}$$

روش نقطه میانی

اگر بخواهیم بدانیم مهم‌ترین تفاوت روش مستطیلی و روش نقطه میانی در محاسبات عددی چیست، کافی است به‌جای $$x_{j-1}$$

$$int_{0}^{1} f(x) dx simeq h sum_{j=1}^N f(x_{j-frac{1}{2}}) + O (h^2)$$

این رابطه بیان می‌کند که تابع $$f$$ دو مرتبه مشتق‌پذیر است، چون $$f^{”}$$

اگر تابع $$f(x)$$ روی بازه بسته‌ای به شکل $$[a,b]$$ تعریف شده باشد و بتوانیم این بازه را به $$n$$ زیربازه با طول مساوی به شکل $$triangle x= frac{b-a}{n}$$

$$int_{a}^{b} f(x) dx approx sum_{i=1}^n f(frac{x_{i-1}+x_i}{2}) triangle x$$

در عمل روش‌های تقریبی زمانی کاربرد درستی خواهند داشت که بدانیم مقدار دقیق انتگرال چقدر است. می‌دانیم وقتی که پاسخ تقریبی یک انتگرال را به‌دست آوردیم، مقدار خطای محاسبات برابر است با اختلاف بین مقدار واقعی و مقدار تقریبی انتگرال. در هر روش تقریبی که در این بخش معرفی می‌کنیم، بهتر است که کران‌ خطا را نیز تعریف کنیم. مقدار کران خطا از خطای واقعی باید بزرگتر باشد. برای مثال، اگر $$A$$ پاسخ تقریبی انتگرالی و $$E$$ کران خطای متناظر با این پاسخ باشد، در این صورت مطمئن هستیم که مقدار واقعی انتگرال همواره بین دو مقدار $$A-E$$

همچنین در مورد محاسبه تقریبی انتگرال‌های عددی مطلوب این است که خطا تابعی از $$triangle x$$ و به‌صورت $$E = E($$

فرض کنید تابع $$f$$ دارای مشتق دومی به‌صورت $$f^{”}$$

$$E (triangle x)= frac{b-a}{24} M (triangle x)^2 = frac{(b-a)^3}{24n^2} M$$

یکی دیگر از روش‌های تقریبی با دقتی از مرتبه دوم، روش ذوزنقه‌ای است که در بخش بعد متوجه خواهید شد روش استفاده از آن در محاسبات عددی چیست.

روش ذوزنقه‌‌ ای

برخلاف روش مستطیلی و روش نقطه میانی که در هر دو از مستطیل‌ها برای تقریب زدن و حل انتگرال عددی استفاده می‌کردیم، در روش ذوزنقه‌ای با در نظر گرفتن تعداد زیادی ذوزنقه در بازه $$[x_{j-1},x_j]$$

$$frac{h (f(x_{j-1})+ f(x_{j}) )}{2}$$

اگر بخواهیم این مقدار را با انتگرال $$f$$ روی همان بازه مقایسه کنیم، با در نظر گرفتن بسط تیلور کوتاه شده به شکل دو جمله خواهیم داشت:

$$f (x) = f(x_{j-1}) + f^{‘} (x_{j-1}) (x-x_{j-1}) + O(h^2)$$

$$f (x_{j}) = f(x_{j-1}) + f^{‘} (x_{j-1}) h + O(h^2)$$

که دومین مشتق $$f$$ در این عبارت در علامت $$O$$ بزرگ قرار گرفته است. با انتگرال‌گیری از رابطه اول خواهیم داشت:

$$int_{x_{j-1}}^{x_j} f (x) dx = hf(x_{j-1}) + frac{h^2}{2} f^{‘} (x_{j-1}) + O(h^3)$$

از طرفی اگر $$f (x_{j}) = f(x_{j-1}) + f^{‘} (x_{j-1}) h + O(h^2)$$

$$frac{h (f(x_{j-1})+ f(x_{j}) )}{2} = h f(x_{j-1}) + frac{h^2}{2} f^{‘} (x_{j-1}) + O(h^3)$$

بنابراین می‌توانیم بنویسیم:

$$int_{x_{j-1}}^{x_j} f (x) dx = frac{h}{2} (f(x_{j-1}) +f(x_{j})) + O(h^3)$$

حالا با جمع‌بندی روی $$j$$ خواهیم داشت:

$$int_{0}^{1} f (x) dx = frac{h}{2} f(0) + h sum_{j=1}^{N-1} f(x_{j}) +frac{h}{2} f(1) +O(h^2)$$

بنابراین روش ذوزنقه‌ای هم یک روش تقریبی از مرتبه دوم است. در شکل‌‌های زیر محاسبه تقریبی مساحت زیر یک منحنی به دو روش مستطیلی و ذوزنقه‌ای با هم مقایسه شده‌ و واضح است که روش ذوزنقه‌ای تقریب دقیق‌تری است:

یک روش دیگر برای بررسی جزئی روش ذوزنقه‌ای این است که مانند روش نقطه میانی در بخش قبل، بازه موردنظر خود را به به $$n$$ زیربازه با طول مساوی به شکل $$triangle x= frac{b-a}{n}$$

$$frac{ f(x_{i})+ f(x_{i+1})}{2} triangle x$$

که با جمع کردن مساحت تمام این ذوزنقه‌ها خواهیم داشت:

$$frac{ f(x_{0})+ f(x_{1})}{2} triangle x +frac{ f(x_{1})+ f(x_{2})}{2} triangle x + … + frac{ f(x_{n-1})+ f(x_{n})}{2} triangle x$$

با ساده‌سازی عبارت بالا خواهیم داشت:

$$triangle x [frac{ f(x_{0})}{2} + f(x_{1})+ f(x_{2}) + … + f(x_{n-1})+ frac{f(x_{n})}{2} ]$$

$$frac{ triangle x }{2}[ f(x_{0}) + 2f(x_{1})+ 2f(x_{2}) + … + 2 f(x_{n-1})+ f(x_{n})]$$

پس قاعده ذوزنقه‌ای برای محاسبه انتگرال عددی با فرضیاتی کاملا مشابه با قاعده نقطه میانی اما با نتیجه‌ای متفاوت و به شکل زیر تعریف می‌شود:

اگر تابع $$f(x)$$ روی بازه بسته‌ای به شکل $$[a,b]$$ تعریف شده باشد و بتوانیم این بازه را به $$n$$ زیربازه با طول مساوی به شکل $$triangle x= frac{b-a}{n}$$

$$int_{a}^{b} f(x) dx approx frac{ triangle x }{2}[ f(x_{0}) + 2f(x_{1})+ 2f(x_{2}) + … + 2 f(x_{n-1})+ f(x_{n})]$$

همان‌طور که در مورد روش نقطه میانی کران خطا را تعیین کردیم، در اینجا هم کران خطا را به شکل زیر تعریف می‌کنیم:

فرض کنید تابع $$f$$ دارای مشتق دومی به‌صورت $$f^{”}$$

$$E (triangle x)= frac{b-a}{12} M (triangle x)^2 = frac{(b-a)^3}{12n^2} M$$

نکته: مزیت روش ذوزنقه‌ای در مقایسه با سایر روش‌های تقریبی برای محاسبه انتگرال‌ها در محاسبات عددی این است که قسمت بالا یا نوک ذوزنقه طبق شکل بالا می‌تواند تقریب خیلی خوبی از بخش خمیده شده یا ماکزیمم منحنی تابع داده شده به ویژه در شرایطی که $$triangle x$$ خیلی کوچک می‌شود، ارائه دهد. این در حالی است که در روش‌های تقریبی مستطیلی چنین تقریبی برای این ناحیه نمی‌توانیم داشته باشیم.

روش سیمپسون

در انتهای بخش قبل تاکید کردیم که مزیت کاربرد روش ذوزنقه‌ای در مقایسه با روش‌های تقریب مستطیلی مانند روش نقطه میانی به جهت محاسبه تقریبی انتگرال‌ها در محاسبات عددی چیست. حال اگر به‌جای استفاده از اشکال هندسی با اضلاعی با خطوط راست و مستقیم مانند مستطیل یا ذوزنقه، دنبال تقریب نزدیکتری به منحنی تابع داده شده باشیم، احتمالا از قاعده سیمپسون استفاده کرده‌ایم. عموما بهترین شکلی که می‌توانیم برای این روش تقریبی انتخاب کنیم، سهمی است. اگر بخشی از منحنی تابع داده شده در زیر انتگرال را با یک سهمی به معادله $$y = ax^2 + bx +c$$

پیش از ادامه این مبحث، بهتر است یادآوری کنیم فرادرس در همین زمینه دوره‌ای با عنوان فیلم آموزش انتگرال عددی با قواعد ذوزنقه‌‌ای و سیمپسون – پیاده‌ سازی در متلب را تهیه کرده است که با مشاهده این دوره می‌توانید پیاده‌سازی این روش را در متلب نیز فرابگیرید. لینک این آموزش در ادامه برای شما قرار داده شده است:

می‌دانیم بین هر دو نقطه انتخابی تعداد بی‌نهایت سهمی می‌توان رسم کرد، اما بین سه نقطه فقط می‌توانیم یک سهمی رسم کنیم. بنابراین اگر بتوانیم بین سه نقطه متوالی روی منحنی مانند $$(x_{i} , f(x_{i}))$$

حالا اگر بازه بسته $$[a,b]$$ را به تعداد زوجی زیربازه تقسیم کنیم، می‌توانیم منحنی تابع را با چند سهمی جایگزین تقریب بزنیم که هر کدام بخشی از زیربازه‌های ایجاد شده را پوشش می‌دهد. اما اول باید فرمول مساحت زیر یک منحنی سهمی شکل را بدانیم. برای به‌دست آوردن چنین فرمولی لازم است معادله سهمی یعنی $$y = ax^2 + bx +c$$

ابتدا باید سه معادله زیر را برای $$a,b,c$$

$$f(x_i) = a (x_{i+1}-triangle x)^2 + b (x_{i+1}-triangle x) + c$$

$$f(x_{i+1}) = a (x_{i+1})^2 + b x_{i+1} + c$$

$$f(x_{i+2}) = a (x_{i+1}+triangle x)^2 + b (x_{i+1}+triangle x) + c$$

حل این سه معادله برای پیدا کردن سه مجهول $$a,b,c$$

$$int_{x_{i+1}-triangle x}^{x_{i+1}+triangle x} (ax^2 + bx +c) dx = frac{triangle x}{3} (f(x_{i}) + 4f(x_{i+1}) + f(x_{i+2}))$$

بنابراین اگر بخواهیم مجموع مساحت زیر تمام سهمی‌ها را حساب کنیم، باید عبارت زیر را به‌دست آوریم:

$$frac{triangle x}{3} (f(x_{0}) + 4f(x_{1}) + f(x_{2}) +f(x_{2}) + 4f(x_{3}) + f(x_{4}) + … +f(x_{n-2}) + 4f(x_{n-1}) + f(x_{n}) )$$

که در حالت ساده‌تر می‌شود:

$$frac{triangle x}{3} (f(x_{0}) + 4f(x_{1}) + 2f(x_{2}) + 4f(x_{3}) + 2f(x_{4}) + … +2f(x_{n-2}) + 4f(x_{n-1}) + f(x_{n}) )$$

بنابراین مشاهده می‌کنید که محاسبات برای روش سیمپسون با محاسبات روش ذوزنقه‌ای بسیار متفاوت است. نکته مهم این است که در فرمول بالا نباید ضرایب دو و چهار را فراموش کنیم. همچنین دقت کنیم که بازه موردنظر خود را به تعداد زوجی زیربازه تقسیم کنیم نه تعداد فرد.

بنابراین تعریف دقیق قاعده سیمپسون به این صورت است:

فرض کنید تابع $$f(x)$$ روی بازه بسته‌ای به شکل $$[a,b]$$ تعریف شده باشد و بتوانیم این بازه را به $$n$$ زیربازه با طول مساوی به شکل $$triangle x= frac{b-a}{n}$$

$$int_{a}^{b} f(x) dx approx frac{ triangle x }{3}[ f(x_{0}) +4f(x_{1})+ 2f(x_{2}) +4f(x_{3}) + … + 2f(x_{n-2}) + 4f(x_{n-1}) + f(x_{n})]$$

همان‌طور که در مورد روش ذوزنقه‌ای کران خطا را تعیین کردیم، در اینجا هم کران خطا را به شکل زیر تعریف می‌کنیم:

فرض کنید تابع $$f$$ دارای مشتق چهارمی به‌صورت $$f^{(4)}$$ در هر نقطه از بازه $$[a,b]$$ است و برای تمام $$x$$‌های این بازه همواره عبارت $$|f^{(4)}(x)| leq M$$

$$E (triangle x)= frac{b-a}{180} M (triangle x)^4 = frac{(b-a)^5}{180n^4} M$$

با توجه به فاکتور $$180n^4$$، کران خطا در این روش دقت بسیار بالاتری نسبت به همتای خود در روش ذوزنقه‌ای یا نقطه میانی دارد. در ادامه این بخش با حل چند مثال بهتر یاد می‌گیریم که تفاوت‌های این روش‌های تقریبی در حل مسائل محاسبات عددی چیست.

حل مثال از روش‌های انتگرال گیری عددی

در انتهای این بخش چند مثال برای شما در نظر گرفته‌ایم تا با بررسی و حل آن‌ها کاملا به روش‌های مختلف انتگرال‌گیری عددی در محاسبات عددی مسلط شوید.

مثال ۱‍

انتگرال تابع $$f(x) =x^2$$

پاسخ

می‌دانیم حاصل این انتگرال با استفاده از فرمول‌‌های انتگرال‌گیری برابر است با $$int_{0}^{1} x^2 dx = frac{x^3}{2+1} |_{0}^{1} =frac{1}{3}$$

$$int_{0}^{1} x^2 dx simeq frac{1}{4}[ 0 + frac{1}{4^2} +frac{1}{2^2} +frac{3^2}{4^2} ] = frac{14}{64} = 0.2188…$$

این عدد از $$frac{1}{3}$$

$$int_{0}^{1} x^2 dx simeq frac{1}{4}[ frac{1}{2} .0 + frac{1}{4^2} +frac{1}{2^2} +frac{3^2}{4^2} + frac{1}{2} .1 ] = frac{22}{64} = 0.3438…$$

این جواب به $$frac{1}{3}$$

مثال ۲

حاصل انتگرال $$int_{0}^{1} e^{-x^2} dx$$

پاسخ

ابتدا مشتق دوم را برای تابع زیر انتگرال پیدا می‌کنیم که طبق فرمول‌‌های مشتق‌گیری برابر می‌شود با:

$$f^{”} (x) = (4x^2-2) e^{-x^2}$$

بنابراین همین جا می‌توانیم به این نتیجه برسیم که روی بازه بسته $$[0,1]$$، تابع $$|f^{”} (x)|$$

$$frac{1}{12} (2) frac{1}{n^2} < 0.005$$

$$frac{1}{6} (200) < n^2$$

$$5.77 approx sqrt{frac{100}{3}}< n$$

با در نظر گرفتن $$n=6$$

$$int_{a}^{b} f(x) dx approx frac{1}{6}[ frac{f(0)}{2} + f(frac{1}{6} )+ f(frac{2}{6} ) + … + f(frac{5}{6} )+ frac{f(1)}{2} ] approx 0.74512$$

راه‌حل چنین مشکلی این است که $$n$$ بزرگتری انتخاب کنیم. برای مثال، با در نظر گرفتن $$n=12$$

$$frac{1}{12} (2) frac{1}{n^2} < 0.001$$

$$frac{1}{6} (1000) < n^2$$

$$12.91 approx sqrt{frac{500}{3}}< n$$

بنابراین بلافاصله می‌توانستیم نتیجه‌گیری کنیم که $$n=13$$

مثال ۳

حاصل انتگرال $$int_{0}^{1} e^{-x^2} dx$$

پاسخ

مشتق چهارم تابع زیر انتگرال برابر می‌شود با:

$$f^{(4)} (x) = (16x^4-48x^2+12) e^{-x^2}$$

بنابراین روی بازه بسته $$[0,1]$$، تابع $$|f^{(4)} (x)|$$ دارای مقدار ماکزیممی به اندازه $$12$$ است. حالا شروع می‌کنیم به پیدا کردن تعداد زیربازه‌هایی که برای تقریب زدن این انتگرال نیاز داریم. برای اینکه حاصل انتگرال را تا دومین رقم اعشار به‌دست آوریم، قطعا باید $$E (triangle x) < 0.005$$

$$frac{1}{180} (12) frac{1}{n^4} < 0.001$$

$$frac{1}{3} (200) < n^4$$

$$2.86 approx sqrt [4]{frac{200}{3}}< n$$

چون لازم است تعداد زیربازه‌ها زوج باشند، پس با در نظر گرفتن $$n=4$$

$$[ f(0) + 4f(frac{1}{4} )+ 2f(frac{1}{2} ) + 4f(frac{3}{4} ) + f(1)] frac{1}{3.4} approx 0.746855$$

بنابراین مقدار واقعی انتگرال عددی است که بین دو مقدار $$0.746855 – 0.0003 = 0.746555$$

مثال ۴

پاسخ تقریبی انتگرال زیر را به دو روش ذوزنقه‌ای و سیمپسون و با در نظر گرفتن چهار زیربازه محاسبه کنید:

$$int_{2}^{4} x^3 dx$$

پاسخ

روی بازه بسته $$[2,4]$$ با در نظر گرفتن $$n=4$$

$$triangle x= frac{b-a}{n} = frac{4-2}{4}= frac{1}{2}$$

ابتدا تقریب ذوزنقه‌ای را به شکل زیر محاسبه خواهیم کرد:

$$int_{2}^{4} x^3dx approx frac{1}{4}[ f(2) + 2f(frac{5}{2} )+2 f(3 ) + 2f(frac{7}{2} ) + f(4)]$$

$$int_{2}^{4} x^3dx approx frac{1}{4}[ 2^3 + 2(frac{5}{2} )^3+2 (3)^3 + 2(frac{7}{2} ) ^3+ 4^3] = frac{243}{4}$$

همچنین خطای این تقریب را می‌توانیم به‌صورت زیر تعیین کنیم:

$$E( frac{1}{2}) = frac{8}{12(16)} M = frac{M}{24}$$

که در آن رابطه $$|f^{”} (x) | < M$$

$$f^{”} (x) = 6x$$

می‌بینیم که نامساوی $$|f^{”} (x) | < 6(4)=24$$

$$int_{2}^{4} x^3dx = frac{243}{4} pm 1$$

حالا همین روند را با بکارگیری قاعده سیمپسون امتحان می‌کنیم:

$$int_{2}^{4} x^3dx approx frac{1}{6}[ f(2) + 4f(frac{5}{2} )+2 f(3 ) + 4f(frac{7}{2} ) + f(4)]$$

$$int_{2}^{4} x^3dx = frac{1}{4}[ 2^3 + 4(frac{5}{2} )^3+2 (3)^3 + 4(frac{7}{2} ) ^3+ 4^3] = 60$$

به تفاوت ضرایب در این دو روش و اثری که در نتیجه خواهد داشت، دقت کنید. با توجه به اینکه $$|f^{(4)}| = 0$$

دیفرانسیل‌ گیری عددی

در بخش قبل این موضوع را بررسی کردیم که انواع روش‌های تقریبی محاسبه انتگرال در محاسبات عددی چیست. در این بخش می‌خواهیم ببینیم روش‌های مشابه مشتق‌گیری تقریبی در محاسبات عددی چیست. ساده‌ترین روش محاسبه تقریبی مشتق $$u^{‘} (x_j)$$

• تفاضل‌های راست و چپ یا تفاضل یک‌طرفه

$$triangle_{+}u_j = frac{u_{j+1} – u_j}{h}$$

$$triangle_{-}u_j = frac{u_{j} – u_{j-1}}{h}$$

• تفاضل مرکزی دو طرفه

$$triangle_{0}u_j = frac{u_{j+1} – u_j}{2h}$$

حالا می‌خواهیم دقت این تفاضل‌ها را در مشتق‌های تقریبی و در شرایطی که $$h rightarrow 0$$

$$u(h) = u (0) + hu^{‘}(0) + frac{h^2}{2} u^{”} (xi)$$

فراموش نمی‌کنیم که $$xi epsilon [0,h]$$. با جایگزینی این عبارت در فرمول تفاضل راست خواهیم داشت:

$$triangle_{+}u_j = frac{u_{h} – u_0}{h} = u^{‘}(0) + frac{h}{2} u^{”} (xi)$$

مادامی که تابع دارای دو مشتق مرزی است، خطا در این عبارت با $$O (h)$$ مشخص می‌شود. به همین خاطر می‌گوییم تفاضل راست روشی از مرتبه اول است. بررسی تفاضل چپ هم به شکل مشابهی است. در مورد تفاضل مرکزی، از دو بسط تیلور حول نقطه صفر برای توابع $$u (h)$$ و $$u (-h)$$ استفاده می‌کنیم. به این ترتیب رابطه‌ای از مرتبه سوم به شکل زیر به‌دست خواهد آمد:

$$u(pm h) = u (0) pm hu^{‘}(0) + frac{h^2}{2} u^{”} (0) pm frac{h^3}{6} u^{”’} (xi)$$

که در آن $$xi$$ بسته به اینکه کدام علامت انتخاب شود می‌تواند جزء بازه $$[0,h]$$ یا $$[-h,0]$$ باشد. با کم کردن $$u(-h)$$ از $$u(h)$$ و حذف جملات شامل $$h^2$$ خواهیم داشت:

$$frac{u_{h} – u_{-h}}{2h} = u^{‘}(0) + frac{h^2}{3} u^{”’} (xi)$$

در این محاسبات خطا از مرتبه $$O(h^2)$$ خواهد بود که نشان دهنده این است که تابع $$u$$ سه مرتبه دیفرانسیل‌گیری می‌شود و در نتیجه این روش یک روش مرتبه دوم است. ساده‌ترین انتخاب برای مشتق دوم، تفاضل دوم مرکزی است:

$$triangle^{2}u_j = frac{u_{j+1} -2 u_j + u_{j-1}}{h^2}$$

که در آن $$triangle^{2} = triangle _+triangle_-= triangle_-triangle_+$$

چون $$triangle^{2}$$ دقت مرتبه دوم است، پس خطا به‌صورت $$O(h^2)$$ خواهد شد. برای اینکه این نکته را ثابت کنیم، بسط تیلور را حول نقطه صفر و برای مرتبه چهارم می‌نویسیم:

$$u(pm h) = u (0) pm hu^{‘}(0) + frac{h^2}{2} u^{”} (0) pm frac{h^3}{6} u^{”’} (0) + frac{h^4}{24} u^{””} (xi)$$

که در آن $$triangle^{2} = triangle _+triangle_-= triangle_-triangle_+$$

$$frac{u_{j+1} -2 u_j +u_{j-1}}{h^2} = u^{”}(0) + frac{h^2}{12} u^{”’} (xi)$$

بنابراین تا زمانی که تابع $$u$$ چهار مرتبه قابلیت دیفرانسیل‌گیری داشته باشد، این روش کاملا $$O(h^2)$$ است. برای مثال، برای تابع $$f(x) = x^2$$

$$f^{‘}(x) = 2x$$

$$f^{”}(x) = 2$$

در نتیجه برای تفاضل راست و چپ و تفاضل مرکزی دوم خواهیم داشت:

$$triangle_{+} f(x) = frac{(x+h)^2 – x^2 }{h} = 2x + h$$

$$triangle_{-} f(x) = frac{x^2 – (x-h)^2 }{h} = 2x – h$$

$$triangle_{0} f(x) = frac{(x+h)^2 – (x-h)^2 }{2h} = 2x$$

$$triangle^2 f(x) = frac{(x+h)^2 – 2x^2 + (x-h)^2 }{h^2} = 2$$

خطا در تفاضل راست برابر است با $$h$$، در حالی که برای تفاضل چپ $$-h$$ می‌شود. پس برای این دو مورد خطا $$O(h)$$ است. همچنین خطا برای $$triangle_{0}$$

درون‌ یابی چیست؟

در سومین بخش از مباحث محاسبات عددی، به توضیح درون‌یابی یا Interpolation می‌پردازیم. اگر بخواهیم مفهوم درون‌یابی را به زبان ساده و با مثال توضیح دهیم، فرض کنید مقادیر مختلف سرعت رو به بالای موشکی به‌صورت تابعی از زمان و در قالب داده‌های نقطه‌ای گسسته در اختیار شما قرار داده شده است. اگر بخواهید سرعت این موشک را در یک زمان خاصی پیدا کنید (با این فرض که این برای این زمان داده‌ای در مورد سرعت ندارید)، می‌توانید از روش درون‌یابی داده‌هایی که در اختیار دارید استفاده کنید.

در عمل روند استفاده از روش درون‌یابی برای پیدا کردن پروفایل یا نحوه تغییرات ارتفاع، سرعت و شتاب یک موشک به این شکل است که یک پروب سرعت در موشک، سرعت آن را در هر لحظه اندازه‌گیری می‌کند. به این ترتیب به کمک این داده‌ها می‌توانیم سرعت موشک را در هر لحظه خاص درون‌یابی کنیم. بنابراین درون‌یابی مسئله‌ فیت کردن یا برازش مجموعه‌ای از نقاط با یک منحنی یا نمودار یک تابع است و در شاخه‌های مختلفی از جمله تحلیل داده، ریاضیات کاربردی، طراحی صنعتی، پردازش سیگنال و تحلیل‌های عددی کاربرد دارد. اگر بخواهیم به زبان آماری صحبت کنیم، درون‌یابی به نوعی محاسبه رگرسیون است. پس در درون‌یابی به دنبال یافتن مقادیر تابع در نقاطی هستیم که برای آن‌ها داده‌ای نداریم و می‌خواهیم با توجه به داده‌هایی که داریم این نقاط را تخمین بزنیم.

در این روش پیدا کردن تابع $$f(x)$$ مناسب چالش اصلی است و اغلب توابع چندجمله‌ای بهترین انتخاب هستند، به این دلیل که ارزیابی، مشتق‌‌گیری و انتگرال‌گیری از این توابع بسیار آسان است. روش‌های مختلف درون‌یابی که در ادامه راجع‌به آن‌ها صحبت خواهیم کرد، عبارت‌اند از:

• درون‌یابی چند جمله‌ای
• درون‌یابی اسپلاین

نکته: اگر $$x$$ جزء دامنه نباشد، در این صورت برای پیدا کردن مقدار $$y$$ متناظر با این $$x$$ باید از برون‌یابی یا Extrapolation استفاده کنیم.

درون‌ یابی چند جمله‌ ای

درون‌یابی چند جمله‌ای یکی از روش‌های محاسبات عددی برای درون‌یابی است که در آن از یک چند جمله‌ای درجه $$N$$ که از $$N+1$$

• درون‌یابی مستقیم یا روش چند جمله‌ای وندرموند
• روش نیوتن
• درون‌یابی لاگرانژ

با توجه به اینکه در مطلب «درون یابی نیوتن – به زبان ساده» از مجله فرادرس این روش کاملا توضیح داده شده است، در ادامه این بخش فقط به توضیح دو روش دیگر پرداخته‌ایم.

درون‌ یابی مستقیم یا روش چند جمله‌ ای وندرموند

فرض کنید $$N+1$$

می‌دانیم تعریف یک چند جمله‌ای درجه $$N$$ و با ضرایبی به‌صورت $$a_0, …, a_N$$

$$p_N (x) = sum_{n=0}^N a_nx^n$$

ابتدا باید تعداد درجات آزادی در چند جمله‌ای با تعداد نقاطی که می‌خواهیم تابع با آن‌ها فیت شود، هماهنگ باشد. سپس برای اینکه ببینیم روش مستقیم و عددی حل مسئله درون‌یابی در محاسبات عددی چیست، تعریف زیر را در نظر می‌گیریم:

$$y_j = sum_{n=0}^N a_nx_j^n$$

این عبارت برای کلیه $$j = 0,…,N$$

$$V a = y Leftrightarrow sum_{n=0}^N V_{jn}a_n = y_j$$

در رابطه بالا $$V$$ «ماتریس وندرموند» نام دارد که به شکل زیر تعریف می‌شود:

$$V_{jn}= x_j^n$$

در ادامه با کاربرد یک نرم‌افزار عددی مانند متلب می‌توانیم شکل برداری $$x_j$$

نکته ۱: اگر از یک چند جمله‌ای خطی برای درون‌یابی مستقیم استفاده کنیم، در این صورت درون‌یابی خطی انجام داده‌ایم.

نکته ۲: اگر از یک چند جمله‌ای درجه دو برای درون‌یابی مستقیم استفاده کنیم، در این صورت درون‌یابی مربعی انجام داده‌ایم.

درون‌ یابی چند جمله‌ ای به روش لاگرانژ

در این قسمت توضیح می‌دهیم که چگونه می‌توانیم مسئله درون‌یابی چند جمله‌ای را در محاسبات عددی به کمک روش لاگرانژ حل کنیم. ابتدا خطای درون‌یابی را بر اساس نرم یکنواخت اختلاف $$f(x) – p_N(x)$$

$$|| f – p_N|| _{infty} := max _x |f(x) – p_N(x)|$$

که در آن ماکزیمم روی بازه بسته $$[x_0,x_N]$$

$$L_k(x_j) = delta _{jk} = begin{cases}1 & j=k\0 & jneq kend{cases}$$

در این روند با ثابت در نظر گرفتن $$k$$ می‌توانیم بگوییم $$L _k$$

$$L _k = C prod_{jneq k} (x-x_j)$$

با ارزیابی این عبارت در $$x=x_k$$

$$1 = C prod_{jneq k} (x_k-x_j)$$

$$C = frac{1}{prod_{jneq k} (x_k-x_j)}$$

بنابراین تنها عبارت ممکن برای $$L_k(x)$$

$$L_k(x) = frac{prod_{jneq k} (x-x_j)}{prod_{jneq k} (x_k-x_j)}$$

این چند جمله‌ای‌های اولیه اساس بسط هر چند جمله‌ای را تشکیل می‌دهند. در بخش مثال‌ها بهتر متوجه کاربرد این روابط خواهید شد.

قضیه درون‌یابی لاگرانژ: اگر $$left{ x_j, j = 0, … , N right}$$