خطای گرد کردن نسبی

Question

فرض کنید$x0,...xn$ اعداد ماشین مثبت در یک کامپیوتر باشد که واحد خطای گرد کردن ان $ \varepsilon $ باشد ثابت کنید خطای گرد کردن نسبی در محاسبه $ \sum xi $ که i= 0,...,n به طریق معمولی حداکثر $(1+ \varepsilon )^n-1$ می باشد و این مقدار تقریبا برابر $n \varepsilon $ است

Comments

@kazomano اگر مقدمهٔ کتاب را بخوانید خود نویسندگان اشاره داشته‌اند که این کتاب حاصل تدریس‌هایشان در چندین دانشگاه آمریکایی و آلمانی است برای یک دورهٔ یک ساله مقدماتی در آنالیز عددی. این یعنی دو درس کارشناسی در آنالیز عددی (برای دو ترم). و بیشتر از آن اینکه دقیقا بلافاصله تأکید می‌کنند که فصل یک باید در ابتدا گفته شود و سپس در فصل‌های پسین چند بخش هستند که در درس مقدماتی سرفصل نیستند و اضافه‌تر گفته شده‌اند. اما نکته اینجاست که دقیقا می‌گویند در فصل‌های بعدی که یعنی غیر از فصل یک! هیچ فردی در هیچ نظام استانداردی، مطالب این فصل یک را در سرفصل‌های درس آنالیز عددی پیشرفته قرار نمی‌دهد. یک استاد درس آنالیز عددی پیشرفته کاملا این حق را دارد که تمام این مطلب را دانسته فرض کند. اگر بر روی آن زمان گذاشت که کاری اضافه کرده‌است (نمی‌گویم کار بدی است ولی جزء سرفصل نیست) و وظیفه‌اش نبوده‌است! اگر هم می‌گوئید در درس آنالیز عددی پیشرفته نتایج و ابزارها و تعاریف این فصل استفاده شده‌اند، که این هیچ جای تعجبی ندارد. همیشه مطالب درس‌های پیش‌نیاز در درس استفاده می‌شوند. ولی این به این معنا نیست که جزو سرفصل‌های این درس هستند. پیرامون سخت بودن، اگر تمرینی سخت باشد دلیل بر جزو سرفصل درس بعدی بودن نمی‌شود. اینکه بدانیم به کدام مبحث مربوط می‌شود اینگونه تشخیص داده می‌شود که آیا با مطالب و مفاهیم فلان درس قابل حل هستند یا خیر. همان گونه هم که خود نویسنده‌ها گفتند در فصل‌های ۲ به بعد (نه یک!) بخش‌هایی هستند که جزو دروس مقدماتی آنالیز عددی نیستند. برای نمونه اسپلاین‌ها سرفصل اصلی درس آنالیزعددی یک نیستند. به نظر من کتاب روانی است، نمی‌دانم منظورتان از سختی در این مورد چه هست.

---

اگه اجازه بدید من هر دو برچسب رو میزارم هم آنالیز عددی و هم پیشرفته. و همچنان خواهید دید که زمین بر مدارش باقی میمونه و اتفاق خاصی نمیفته :)

---

@kazomano این پرسش را پیش‌تر پرسیده‌بودید؟ در دیدگاه‌های پیشین ندیدم درخواست کتاب مشابه کرده‌باشید. کتاب آنالیز عددی ۱ نوشتهٔ اسماعیل بابلیان انتشارات پیام نور را که به عنوان یک مرجع برای نخستین درس در آنالیز عددی در نظام آموزشی ایران قبول دارید؟ تمام ابزاری که برای پاسخ دادن به این پرسش نیاز است یعنی خطای نسبی، عدد ماشین، گرد کردن ماشین، ممیز شناور و چهار عمل اصلی، در ابتدای این کتاب بحث شده‌اند. آیا ابزار دیگری برای این پرسش نیاز است که در درس مقدماتی آنالیز عددی نیامده‌است؟ اگر بلی، آنگاه با جزو مباحث درس آنالیز عددی پیشرفته بودن موافقت می‌کنم.
بعلاوه اینکه سطح کتاب‌های دیگر از سطح کتاب استوئر پائین‌تر باشد، آیا دلیل بر این می‌شود که ترجمهٔ نام کتاب را اشتباه انجام دهیم؟ نه تنها در مرجع پرسش در بالا اشتباه نوشته‌اند، بلکه در یک جستجوی اینترنتی در گوگل به زبان فارسی می‌بینید تقریبا اکثریت افراد اشتباه نام را می‌نویسند! آیا این کار درست است؟
آنالیز خطا نیز یک مفهوم گسترده‌ای است و تنها شامل مطالب این پرسش نمی‌شود. اینکه چه چیزی در تحلیل خطا (آنالیز خطا) جزو سرفصل‌های آنالیز عددی پیشرفته است (ابزارهایی که آنجا معرفی می‌شوند و در آنالیز عددی کارشناسی نیستند) اینجا مهم است. در ضمن واژهٔ تحلیل خطا بحث خطای الگوریتم‌هایی که معرفی می‌کنید را نیز شامل می‌شود. خود به خود زمانی که در آنالیز عددی یک روش جدید معرفی می‌کنید، آنالیز خطایش را نیز در ادامه‌اش بحث می‌کنید.

---

امیدوارم با این تغییر جدید مشکلتون حل شده باشه

---

@Hanieh
لطفا دیدگاههای مفید بذارید. این دیدگاه شما چه مشکلی رو حل میکنه.

Answer 1

$$ S_{n}= x_{1} + x_{2} +...+ x_{n}, S^{*} _{n}=fl( S_{n} ) \\ S_{1} = x_{1}, S^{*} _{1}=fl( x_{1} )=x_{1} \\ S_{j+1} = S_{j} + x_{j+1}, S^{*} _{j+1}=fl(S^{*} _{j}+ x_{j+1} ) \\ p_{n+1} = \frac{S^{*} _{n+1}-S_{n+1}}{S_{n+1}} ,| \delta _{k} | \leq \varepsilon\\ p_{n+1} = \frac{fl(S^{*} _{n}+ x_{n+1})-(S_{n} + x_{n+1})}{S_{n+1}}\\ p_{n+1}= \frac{(S^{*} _{n}+ x_{n+1})(1+ \delta _{n} )-(S_{n} + x_{n+1})}{S_{n+1}} \\ p_{n+1}= \frac{(S_{n}(1+ \rho _{n} )+x_{n+1})(1+ \delta _{n} )-(S_{n} + x_{n+1})}{S_{n+1}}\\ p_{n+1}= \frac{S_{n} \rho _{n}+ \delta _{n}S_{n}+S_{n} \rho _{n} \delta _{n}+ x_{n+1} \delta _{n}}{S_{n+1}}\\ p_{n+1}= \frac{\delta _{n}(S_{n} + x_{n+1})+ \rho _{n}(S_{n}+S_{n}\delta _{n}}{S_{n+1}}\\ p_{n+1}= \frac{\delta _{n}S_{n+1}+ \rho _{n}S_{n}(1+\delta _{n})}{S_{n+1}} \\ p_{n+1}=\delta _{n}+ \rho _{n}( \frac{S_{n}}{S_{n+1}} )(1+\delta _{n}) $$

حالا چون اعداد ما مثبت بودن و $ S_{n} \leq S_{n+1} $ داریم

$$ |p_{n+1}| \leq \varepsilon +| \rho _{n}|(1)(1+ \varepsilon)= \varepsilon+ \Psi | \rho _{n}| s.t , \Psi =1+ \varepsilon $$

حالا داریم

$$ |p_{1}|=0 , |p_{2}| \leq \varepsilon , |p_{3}| \leq \varepsilon+ \Psi \varepsilon , |p_{4}| \leq \varepsilon+ \Psi \varepsilon+ \Psi ^{2} \varepsilon\\ |p_{n}| \leq \varepsilon+\Psi \varepsilon+...\Psi ^{n-1} \varepsilon= \varepsilon (1+ \Psi +...+ \Psi ^{n-1}) \\ |p_{n}| \leq \varepsilon ( \frac{ \Psi ^{n} -1}{ \Psi -1} )= \varepsilon ( \frac{ (1+ \varepsilon )^{n}-1 }{1+ \varepsilon -1} )= (1+ \varepsilon )^{n} -1 \simeq n \varepsilon $$

Comments

@kazomano اگر با فرض $fl(x_i)=x_i$ جلو برویم آنگاه $fl(S_n)=S_n$ و از ابتدا تا انتها تقریبی نخواهیم داشت و خطا دقیقا صفر است و به دنبال آن خطای نسبی نیز صفر می‌شود.

---

@AmirHosein
فقط اولیه که ماشین میتونه به اینصورت بنویسه.و برای جمع های بعدی به اینصورت نیست.یعنی وقتی ماشین دو عدد رو جمع میکنه خطای گرد کردن داریم و برای جمع سه عدد ماشین به صورت
fl(x1+x2+x3)=fl(fl(x1+x2)+x3) عمل میکنه و هربار مرتکب خطا میشه و همینطور الی آخر.

---

ببخشید در بین بحث شما اینو میگم. @kazomano برای تایپ ریاضی چند عبارت زیر هم کافی است از \\ برای رفتن به خط بعدی استفاده کنید لطفا اینجا را ببینید: http://math.irancircle.com/56/%D8%B1%D8%A7%D9%87%D9%86%D9%85%D8%A7%DB%8C-%DA%A9%D9%84%DB%8C-%D8%AA%D8%A7%DB%8C%D9%BE-%D8%B1%DB%8C%D8%A7%D8%B6%DB%8C?show=5204#a5204

---

@kazomano حواسم به نمایش محدود نبود، داشتم به گرد کردن معمولی فکر می‌کردم. در آن صورت جمع یک سری عدد که از یک رقم به پائین ندارند (در هر مبنایی که کار می‌کنید)، هرگز نمی‌تواند دارای رقمی پائین‌تر از رقمی باشد که از آنجا به پائین را گرد کرده‌اید. مسلما اگر به حالت ممیز شناور و نمایش محدود برویم قضیه فرق می‌کند. اما پیرامون $\delta$ و $\rho$، قرارداد جهانی نیستند و ندیده‌ام جایی این نمادها را رذرف کنند، برای نمونه در همین کتاب آقای جوزف استوئر که یکی از مرجع‌های معروف است، چنین قراردادی را نمی‌بینید!

---

@AmirHosein
نماد دلتا و رو در همون کتاب استوئر وجود داره ولی اونجا rd مینویسه. البته بعدش همون فلات رو هم نوشته.و به جای دلتا از اپسیلون و به جای اپسیلون از eps به عنوان دقت ماشین استفاده میکنه.