قضیه نقطه ثابت

در ریاضیات، قضیه نقطه ثابت یا تکرار ساده (به انگلیسی: Fixed-point theorem) قضیه‌ای است که می‌گوید در صورت برآورده‌شدن پاره‌ای از شرایط می‌توان اطمینان حاصل کرد که تابع F حداقل یک نقطهٔ ثابت مانند x دارد. منظور از نقطهٔ ثابت نقطه‌ای است که در آن $F(x)=x$ است.^[۱]

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

در آنالیز ریاضی

قضیه نقطه ثابت باناخ (۱۹۹۲) معیاری کلی ارائه می‌دهد که اگر برقرار باشد، فرایند تکرار یک تابع به نقطه ثابت منجر می‌شود. نقطه ثابت نقطه‌ای است که وقتی تابع روی آن اعمال می‌شود، مقدارش تغییر نمی‌کند. به عبارت دیگر، اگر f یک تابع باشد، نقطه x نقطه ثابت است اگر f(x)=x.^[۲]

در مقابل، قضیه نقطه ثابت بروئر (۱۹۱۱) یک نتیجه غیرسازنده است: این قضیه بیان می‌کند که هر تابع پیوسته از یک توپ بسته در فضای اقلیدسی n-بعدی به خودش باید یک نقطه ثابت داشته باشد، اما روشی برای یافتن نقطه ثابت ارائه نمی‌دهد.^[۳] به عنوان مثال، تابع کسینوس در بازه [−۱٬۱] پیوسته است و این بازه را به خودش نگاشت می‌کند، بنابراین باید یک نقطه ثابت داشته باشد. اگر نمودار تابع y=cos⁡(x) را رسم کنیم، نقطه ثابت جایی است که این نمودار خط y=x را قطع می‌کند. این نقطه ثابت که به عنوان عدد داتی (Dottie number) شناخته می‌شود، تقریباً برابر با x=۰٫۷۳۹۰۸۵۱۳۳۲۱۵۱۶ است.

قضیه نقطه ثابت لفشتز^[۴] (و قضیه نقطه ثابت نیلسن^[۵]) از توپولوژی جبری قابل توجه هستند زیرا به نوعی روشی برای شمارش نقاط ثابت ارائه می‌دهند.

تعمیم‌های متعددی برای قضیه نقطه ثابت باناخ وجود دارد که در نظریه معادلات دیفرانسیل با مشتقات جزئی (PDE) به کار می‌روند. همچنین، قضیه کلاژ در فشرده‌سازی بَرخالها ثابت می‌کند که برای بسیاری از تصاویر، توصیف نسبتاً کوچکی از یک تابع وجود دارد که وقتی به‌طور تکراری روی هر تصویر اولیه اعمال شود، به سرعت به تصویر مورد نظر همگرا می‌شود.^[۶]

در جبر و ریاضیات گسسته

در جبر و ریاضیات گسسته، قضیه ناستر-تارسکی بیان می‌کند که هر تابع حفظ‌کننده ترتیب روی یک شبکه کامل، یک نقطه ثابت و در واقع کوچک‌ترین نقطه ثابت دارد.^[۷] این قضیه کاربردهایی در تفسیر انتزاعی، شکلی از تحلیل ایستای برنامه، دارد.

در حساب لامبدا، یک موضوع رایج یافتن نقاط ثابت عبارات لامبدا است. هر عبارت لامبدا یک نقطه ثابت دارد، و یک ترکیب‌کننده نقطه ثابت تابعی است که یک عبارت لامبدا را به عنوان ورودی می‌گیرد و نقطه ثابت آن عبارت را به عنوان خروجی تولید می‌کند.^[۸] یک ترکیب‌کننده نقطه ثابت مهم، ترکیب‌کننده Y است که برای تعاریف بازگشتی استفاده می‌شود.

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

همین تعریف تابع بازگشتی را می‌توان در نظریه محاسبه‌پذیری با اعمال قضیه بازگشتی کلین ارائه داد.^[۹] این نتایج معادل نیستند؛ قضیه ناستر-تارسکی نتیجه بسیار قوی‌تری است نسبت به آنچه در معناشناسی دنوتاسیونال استفاده می‌شود.^[۱۰] با این حال، در پرتو تز چرچ-تورینگ، معنای شهودی آنها یکسان است: یک تابع بازگشتی را می‌توان به عنوان کوچک‌ترین نقطه ثابت یک تابعی خاص، که توابع را به توابع نگاشت می‌کند، توصیف کرد.

تکنیک تکرار یک تابع برای یافتن نقطه ثابت را می‌توان در نظریه مجموعه‌ها نیز به کار برد. لم نقطه ثابت برای توابع نرمال بیان می‌کند که هر تابع پیوسته و کاملاً افزایشی از اعداد ترتیبی به اعداد ترتیبی، یک (و در واقع بسیاری) نقطه ثابت دارد.

هر عملگر بستار روی یک مجموعه مرتب جزئی (پوزت) نقاط ثابت زیادی دارد؛ اینها عناصر «بسته» نسبت به عملگر بستار هستند و دلیل اصلی تعریف عملگر بستار در وهله اول همین است.

هر برگشت روی یک مجموعه متناهی با تعداد فردی از عناصر، یک نقطه ثابت دارد؛ به‌طور کلی، برای هر برگشت روی یک مجموعه متناهی از عناصر، تعداد عناصر و تعداد نقاط ثابت دارای همان زوجیت هستند. دُن زیگر از این مشاهدات برای ارائه یک اثبات یک‌جمله‌ای از قضیه فرما دربارهٔ مجموع دو مربع استفاده کرد، با توصیف دو برگشت روی یک مجموعه سه‌تایی از اعداد صحیح، که یکی از آنها به راحتی می‌تواند نشان دهد که فقط یک نقطه ثابت دارد و دیگری برای هر نمایش یک عدد اول داده شده (هم‌نهشت با 1 به پیمانه 4) به عنوان مجموع دو مربع، یک نقطه ثابت دارد. از آنجایی که برگشت اولی تعداد فرد از نقاط ثابت دارد، دومی نیز همینطور است و بنابراین همیشه نمایشی از فرم مورد نظر وجود دارد.^[۱۱]

روش حل معادلات

طریقه استفاده از روش برای حل معالات:

شکل معادله را به صورت $f(x)=x$ در بیاوریم.
عددی دلخواه را به جای $x$ در $f(x)$ قرار می‌دهیم؛ مثلاً k
مقدار $f(k)$ بدست آمده را دوباره به جای $x$ در $f(x)$ قرار می‌دهیم.
عمل فوق را به‌طور نامتناهی انجام می‌دهیم و به جواب نزدیک تر خواهیم شد.

مثال

حل معادله $x^{x}=2$

مرحله اول:

$x^{x}=2$

در نتیجه

$x={\sqrt[{x}]{2}}$

مرحله دوم: مقدار اولیه k=۴

$x={\sqrt[{4}]{2}}=1.1892071500....$

مرحله سوم: k=۱٫۸۹۲۰۷۱۵۰

$x={\sqrt[{1.89207150}]{2}}=1.44244994$

مرحله چهارم: k=۱٫۴۴۲۴۴۹۹۴

$x={\sqrt[{1.44244994}]{2}}=1.616938$

مرحله پنجم: k=۱٫۶۱۶۹۳۸

$x={\sqrt[{1.616938}]{2}}=1.53522$

مرحله ششم: k=۱٫۵۳۵۲۲

$x={\sqrt[{1.53522}]{2}}=1.57006$

پس جواب معاله تا یک رقم اعشار:

$x=1.5...$

با انجام عمل متوالی بالا به تقریب‌های دقیق تری از جواب خواهید رسید.

اثبات روش

به مراحل حل معادله توجه کنید $x=f(x)$

$x=f(f(x))$

$x=f(f(f(x)))$

که دنباله زیر را تشکیل می‌دهند.

$x,\ f(x),\ f(f(x)),\ f(f(f(x))),\dots$

در صورتی که این دنباله واگرا نباشد و همگرا باشد به جواب می‌رسیم.

جستارهای وابسته

نقطه ثابت

منابع

↑ Brown, R. F., ed. (1988). Fixed Point Theory and Its Applications. American Mathematical Society. ISBN 0-8218-5080-6.
↑ Giles, John R. (1987). Introduction to the Analysis of Metric Spaces. Cambridge University Press. ISBN 978-0-521-35928-3.
↑ Eberhard Zeidler, Applied Functional Analysis: main principles and their applications, Springer, 1995.
↑ Solomon Lefschetz (1937). "On the fixed point formula". Ann. of Math. 38 (4): 819–822. doi:10.2307/1968838.
↑ Fenchel, Werner; Nielsen, Jakob (2003). Schmidt, Asmus L. (ed.). Discontinuous groups of isometries in the hyperbolic plane. De Gruyter Studies in mathematics. Vol. 29. Berlin: Walter de Gruyter & Co.
↑ Barnsley, Michael. (1988). Fractals Everywhere. Academic Press, Inc. ISBN 0-12-079062-9.
↑ Alfred Tarski (1955). "A lattice-theoretical fixpoint theorem and its applications". Pacific Journal of Mathematics. 5:2: 285–309.
↑ Peyton Jones, Simon L. (1987). The Implementation of Functional Programming. Prentice Hall International.
↑ Cutland, N.J., Computability: An introduction to recursive function theory, Cambridge University Press, 1980. شابک ‎۰−۵۲۱−۲۹۴۶۵−۷
↑ The foundations of program verification, 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, شابک ‎۰−۴۷۱−۹۱۲۸۲−۴, Chapter 4; theorem 4.24, page 83, is what is used in denotational semantics, while Knaster–Tarski theorem is given to prove as exercise 4.3–5 on page 90.
↑ Zagier, D. (1990), "A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares", American Mathematical Monthly, 97 (2): 144, doi:10.2307/2323918, MR 1041893.

مشارکت‌کنندگان ویکی‌پدیا. «Fixed-point_theorem». در دانشنامهٔ ویکی‌پدیای انگلیسی.
«حل معادلات با تقریب دلخواه»جشنواره جوان خوارزمی، شهریور ۱۳۹۱

پیوند به بیرون

توضیحی برای روش نقطه ثابت

[1] Brown, R. F., ed. (1988). Fixed Point Theory and Its Applications. American Mathematical Society. ISBN 0-8218-5080-6.

[2] Giles, John R. (1987). Introduction to the Analysis of Metric Spaces. Cambridge University Press. ISBN 978-0-521-35928-3.

[3] Eberhard Zeidler, Applied Functional Analysis: main principles and their applications, Springer, 1995.

[4] Solomon Lefschetz (1937). "On the fixed point formula". Ann. of Math. 38 (4): 819–822. doi:10.2307/1968838.

[5] Fenchel, Werner; Nielsen, Jakob (2003). Schmidt, Asmus L. (ed.). Discontinuous groups of isometries in the hyperbolic plane. De Gruyter Studies in mathematics. Vol. 29. Berlin: Walter de Gruyter & Co.

[6] Barnsley, Michael. (1988). Fractals Everywhere. Academic Press, Inc. ISBN 0-12-079062-9.

[7] Alfred Tarski (1955). "A lattice-theoretical fixpoint theorem and its applications". Pacific Journal of Mathematics. 5:2: 285–309.

[8] Peyton Jones, Simon L. (1987). The Implementation of Functional Programming. Prentice Hall International.

[9] Cutland, N.J., Computability: An introduction to recursive function theory, Cambridge University Press, 1980. شابک ‎۰−۵۲۱−۲۹۴۶۵−۷

[10] The foundations of program verification, 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, شابک ‎۰−۴۷۱−۹۱۲۸۲−۴, Chapter 4; theorem 4.24, page 83, is what is used in denotational semantics, while Knaster–Tarski theorem is given to prove as exercise 4.3–5 on page 90.

[11] Zagier, D. (1990), "A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares", American Mathematical Monthly, 97 (2): 144, doi:10.2307/2323918, MR 1041893.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]