จุดตรึง (คณิตศาสตร์)

ในทางคณิตศาสตร์จุดตรึง (บางครั้ง ย่อว่า fixpoint ) หรือที่เรียกว่าจุดไม่เปลี่ยนแปลงคือค่าที่ไม่เปลี่ยนแปลงภายใต้การแปลง ที่กำหนด โดยเฉพาะอย่างยิ่งสำหรับฟังก์ชันจุดตรึงคือองค์ประกอบที่ถูกแปลงไปยังตัวมันเองโดยฟังก์ชันนั้น เซตของจุดตรึงใดๆ ของการแปลงก็เรียกว่าเซตไม่ เปลี่ยนแปลงเช่นกัน
จุดคงที่ของฟังก์ชัน
ตามหลักการแล้วcเป็นจุดตรึงของฟังก์ชันf ก็ ต่อ เมื่อcอยู่ในทั้งโดเมนและโคโดเมนของfและf ( c ) = cโดยเฉพาะอย่างยิ่งfจะไม่มีจุดตรึงใดๆ เลยหากโดเมนของ f แยกออกจากโคโดเมน ถ้าfถูกนิยามบนจำนวนจริงในทางกราฟิกแล้ว f จะสอดคล้องกับเส้นโค้งในระนาบยุคลิดและจุดตรึงc แต่ละจุด จะสอดคล้องกับจุดตัดของเส้นโค้งกับเส้นตรงy = xดังแสดงในภาพ
ตัวอย่างเช่น ถ้าfถูกกำหนดบนจำนวนจริงโดย ดังนั้น 2 จึงเป็นจุดคงที่ของfเพราะ f (2) = 2
ไม่ใช่ทุกฟังก์ชันจะมีจุดตรึง: ตัวอย่างเช่นf ( x ) = x + 1ไม่มีจุดตรึง เพราะx + 1จะไม่เท่ากับxสำหรับจำนวนจริงใดๆ
การวนซ้ำจุดคงที่
ในการวิเคราะห์เชิงตัวเลขการวนซ้ำจุดตรึงเป็นวิธีการคำนวณจุดตรึงของฟังก์ชัน โดยเฉพาะอย่างยิ่ง เมื่อกำหนดฟังก์ชันมาให้ด้วยโดเมนและโคโดเมนเดียวกัน จุดหนึ่งในขอบเขตของการวนซ้ำจุดคงที่คือ
ซึ่งก่อให้เกิดลำดับของการประยุกต์ใช้ฟังก์ชันแบบวนซ้ำซึ่งหวังว่าจะมาบรรจบกันที่จุดหนึ่ง. ถ้าถ้าค่าที่ได้มีความต่อเนื่อง ก็สามารถพิสูจน์ได้ว่าค่าที่ได้นั้นมีความต่อเนื่องเช่นกันเป็นจุดคงที่ของ.
แนวคิดเรื่องจุดคงที่ดึงดูด จุดคงที่ผลักดัน และจุดคาบถูกกำหนดขึ้นโดยสัมพันธ์กับการวนซ้ำของจุดคงที่
ทฤษฎีบทจุดตรึง
ทฤษฎีบทจุดตรึงเป็นผลลัพธ์ที่กล่าวว่ามีจุดตรึงอย่างน้อยหนึ่งจุดภายใต้เงื่อนไขทั่วไปบางประการ[ 1 ]
ตัวอย่างเช่นทฤษฎีบทจุดตรึงของ Banach (1922) ให้เกณฑ์ทั่วไปที่รับประกันว่า หากเป็นไปตามเกณฑ์นี้การวนซ้ำจุดตรึงจะลู่เข้าสู่จุดตรึงเสมอ
ทฤษฎีบทจุดตรึงของบราวเวอร์ (1911) กล่าวว่าฟังก์ชันต่อเนื่อง ใดๆ จากทรงกลมหน่วย ปิด ในปริภูมิยุคลิดมิติnไปยังตัวมันเองจะต้องมีจุดตรึง แต่ไม่ได้อธิบายวิธีการหาจุดตรึงนั้น
ทฤษฎีบทจุดตรึงของเลฟเชตซ์ ( และทฤษฎีบทจุดตรึงของนีลเซน ) จากโทโพโลยีเชิงพีชคณิตให้วิธีการนับจำนวนจุดตรึง
จุดคงที่ของการกระทำของกลุ่ม
ในพีชคณิตสำหรับกลุ่มGที่กระทำต่อเซตXด้วยการกระทำของกลุ่มกล่าวได้ ว่าxในXเป็นจุดคงที่ของgถ้า.
กลุ่มย่อยจุดคงที่ของออโตมอร์ฟิซึมfของกลุ่มGคือกลุ่มย่อยของG :
ในทำนองเดียวกันวงแหวนย่อยจุดคงที่ของออโตมอร์ฟิซึมfของริงRคือซับริงของจุดตรึงของfนั่นคือ
ในทฤษฎีกาโลอิสเซตของจุดตรึงของเซตออโตมอร์ฟิซึมของฟิลด์ หนึ่ง เรียกว่าฟิลด์ตรึงของเซตออโตมอร์ฟิซึม
คุณสมบัติจุดตรึงเชิงทอพอโลยี
ปริภูมิเชิงทอพอโลยีกล่าวได้ว่ามีคุณสมบัติจุดตรึง (FPP) ถ้าสำหรับฟังก์ชันต่อเนื่อง ใดๆ
มีอยู่จริงโดยที่.
FPP เป็นค่าคงที่เชิงทอพอโลยีกล่าวคือ มันถูกรักษาไว้โดยโฮมีโอเมอร์ฟิซึม ใดๆ นอกจากนี้ FPP ยังถูกรักษาไว้โดยการหดกลับ ใดๆ ด้วย
ตามทฤษฎีบทจุดตรึงของ Brouwer เซตย่อยที่กระชับและนูน ทุกเซตในปริภูมิยุคลิดจะมี FPP ความกระชับเพียงอย่างเดียวไม่ได้หมายความถึง FPP และความนูนก็ไม่ใช่คุณสมบัติทางโทโพโลยีด้วยซ้ำ ดังนั้นจึงสมเหตุสมผลที่จะถามว่าจะกำหนดลักษณะทางโทโพโลยีของ FPP ได้อย่างไร ในปี 1932 Borsukถามว่าความกระชับร่วมกับความสามารถในการหดตัวสามารถเป็นเงื่อนไขที่จำเป็นและเพียงพอสำหรับ FPP ได้หรือไม่ ปัญหานี้ยังคงเปิดอยู่เป็นเวลา 20 ปี จนกระทั่ง Kinoshita พิสูจน์ได้ว่าข้อสันนิษฐานนี้ไม่ถูกต้อง โดยเขาพบตัวอย่างของปริภูมิที่กระชับและหดตัวได้โดยไม่มี FPP [ 2 ]
จุดคงที่ของลำดับบางส่วน
ในทฤษฎีโดเมนแนวคิดและศัพท์เฉพาะของจุดตรึงจะถูกขยายไปสู่ลำดับบางส่วนให้ ≤ เป็นลำดับบางส่วนเหนือเซตXและให้f : X → Xเป็นฟังก์ชันเหนือXแล้วจุดตรึงก่อนหน้า (หรือสะกดว่าpre-fixed pointบางครั้งย่อเป็นprefixpointหรือpre-fixpoint ) ของfคือp ใดๆ ที่f ( p ) ≤ p ใน ทำนองเดียวกันจุดตรึงหลัง ของfคือp ใดๆ ที่p ≤ f ( p ) [ 3 ] บางครั้งมีการใช้ในทางตรงกันข้าม[ 4 ] Malkis ให้เหตุผลนิยามที่นำเสนอไว้ที่นี่ดังนี้: "เนื่องจากfอยู่ก่อนเครื่องหมายอสมการในเทอมf ( x ) ≤ xดังนั้นx ดังกล่าว จึงเรียกว่า จุดตรึง ก่อน หน้า " [ 5 ]จุดตรึงคือจุดที่เป็นทั้งจุดตรึงก่อนหน้าและจุดตรึงหลัง จุดตรึงก่อนหน้าและจุดตรึงหลังมีการประยุกต์ใช้ในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี[ 6 ]
จุดคงที่น้อยที่สุด
ในทฤษฎีลำดับจุดตรึงที่เล็กที่สุดของฟังก์ชันจากเซตที่มีลำดับบางส่วน (poset) ไปยังตัวมันเอง คือจุดตรึงที่เล็กกว่าจุดตรึงอื่นๆ ทุกจุด ตามลำดับของ poset นั้น ฟังก์ชันไม่จำเป็นต้องมีจุดตรึงที่เล็กที่สุด แต่ถ้ามี จุดตรึงที่เล็กที่สุดนั้นจะต้องมีเพียงหนึ่งเดียว
วิธีหนึ่งในการแสดงทฤษฎีบท Knaster–Tarskiคือการกล่าวว่าฟังก์ชันโมโนโทนบนแลตทิซที่สมบูรณ์มีจุดตรึงน้อยที่สุดที่ตรงกับจุดพรีฟิกพอยต์น้อยที่สุด (และในทำนองเดียวกัน จุดตรึงมากที่สุดจะตรงกับจุดโพสต์ฟิกพอยต์มากที่สุด) [ 7 ]
ตัวรวมจุดคงที่
ในตรรกศาสตร์เชิงผสมสำหรับวิทยาการคอมพิวเตอร์ ตัวรวมจุดคงที่ (fixed-point combinator) คือฟังก์ชันลำดับสูงกว่าฟังก์ชันนี้จะส่งคืนค่าจุดคงที่ของฟังก์ชันอาร์กิวเมนต์ หากมีอยู่ กล่าวคือ ถ้าฟังก์ชันfมีจุดคงที่ตั้งแต่หนึ่งจุดขึ้นไป แล้ว
ตรรกะจุดคงที่
ในตรรกศาสตร์เชิงคณิตศาสตร์ตรรกศาสตร์จุดตรึง (fixed-point logics) เป็นส่วนขยายของตรรกศาสตร์ภาคแสดงแบบคลาสสิก (classical predicate logic) ที่ถูกนำมาใช้เพื่อแสดงการเรียกซ้ำ (recursion) การพัฒนาตรรกศาสตร์ประเภทนี้ได้รับแรงบันดาลใจจากทฤษฎีความซับซ้อนเชิงพรรณนา (descriptive complexity theory)และความสัมพันธ์กับภาษาการสอบถามฐานข้อมูลโดยเฉพาะอย่างยิ่งกับDatalog
แอปพลิเคชัน
ในหลายสาขา สภาวะสมดุลหรือเสถียรภาพเป็นแนวคิดพื้นฐานที่สามารถอธิบายได้ในแง่ของจุดคงที่ ตัวอย่างบางส่วนมีดังต่อไปนี้
- ในเรขาคณิตเชิงโปรเจกทีฟจุดคงที่ของโปรเจกทีฟเรียกว่าจุดคู่[ 8 ] [ 9 ]
- ในทางเศรษฐศาสตร์สมดุลแนชของเกม คือจุดคงที่ของ ความสัมพันธ์ระหว่างการตอบสนองที่ดีที่สุดของเกมจอห์น แนชได้ใช้ทฤษฎีบทจุดคงที่ของคากุทานิในบทความสำคัญของเขาซึ่งทำให้เขาได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์
- ในฟิสิกส์โดยเฉพาะอย่างยิ่งในทฤษฎีการเปลี่ยนเฟส การทำให้เป็นเชิงเส้นใกล้ จุดคงที่ ที่ไม่เสถียรได้นำไปสู่ ผลงานที่ได้รับรางวัลโนเบลของวิลสัน ในการคิดค้น กลุ่มการปรับมาตรฐานและคำอธิบายทางคณิตศาสตร์ของคำว่า " ปรากฏการณ์วิกฤต " [ 10 ] [ 11 ]
- คอมไพเลอร์ภาษาโปรแกรมใช้การคำนวณจุดคงที่สำหรับการวิเคราะห์โปรแกรม เช่น ในการวิเคราะห์การไหลของข้อมูลซึ่งมักจำเป็นสำหรับการเพิ่มประสิทธิภาพ โค้ด นอกจากนี้ยังเป็นแนวคิดหลักที่ใช้โดยวิธีการวิเคราะห์โปรแกรมทั่วไปที่เรียกว่าการตีความแบบนามธรรม[ 12 ]
- ในทฤษฎีประเภท ตัวรวมจุดตรึงช่วยให้สามารถกำหนดฟังก์ชันแบบเรียกซ้ำได้ในแคลคูลัสแลมบ์ดาที่ไม่มีประเภท
- เวกเตอร์ของ ค่า PageRankของเว็บเพจทั้งหมดเป็นจุดคงที่ของการแปลงเชิงเส้นที่ได้มาจากโครงสร้างลิงก์ของเวิลด์ไวด์เว็บ
- การกระจายแบบคงที่ของลูกโซ่ Markovคือจุดคงที่ของฟังก์ชันความน่าจะเป็นการเปลี่ยนสถานะหนึ่งขั้น
- จุดคงที่ใช้ในการค้นหาสูตรสำหรับฟังก์ชันที่ทำซ้ำ
ดูเพิ่มเติม
หมายเหตุ
- ↑ Brown, RF, บรรณาธิการ (1988). ทฤษฎีจุดตรึงและการประยุกต์ใช้ . สมาคมคณิตศาสตร์อเมริกัน. ISBN 0-8218-5080-6.
- ↑ Kinoshita, Shin'ichi (1953). "On Some Contractible Continua without Fixed Point Property" . Fund. Math. 40 (1): 96– 98. doi : 10.4064/fm-40-1-96-98 . ISSN 0016-2736 .
- ↑ Smyth, Michael B.; Plotkin, Gordon D. (1982). "The Category-Theoretic Solution of Recursive Domain Equations" (PDF) . Proceedings, 18th IEEE Symposium on Foundations of Computer Science . SIAM Journal of Computing (volume 11). pp. 761– 783. doi : 10.1137/0211062 .
- ↑ Patrick Cousot; Radhia Cousot (1979). "เวอร์ชันเชิงสร้างสรรค์ของทฤษฎีบทจุดตรึงของ Tarski" (PDF) . Pacific Journal of Mathematics . 82 (1): 43– 57. doi : 10.2140/pjm.1979.82.43 .
- ↑ Malkis, Alexander (2015). "การตีความเชิงนามธรรมแบบคาร์ทีเซียนหลายเธรดของโปรแกรมเรียกซ้ำหลายเธรดเป็นพหุนาม" ( PDF )ปัญหาการเข้าถึงได้บันทึกการบรรยายในวิทยาการคอมพิวเตอร์ เล่มที่9328 หน้า114–127 doi : 10.1007/978-3-319-24537-9_11 ISBN 978-3-319-24536-2S2CID 17640585เก็บถาวรจากต้นฉบับ(PDF) เมื่อวัน ที่ 10 สิงหาคม 2022
- ↑ Yde Venema (2008)การบรรยายเกี่ยวกับแคลคูลัส μ แบบโมดอล เก็บถาวรเมื่อวันที่ 21 มีนาคม 2012 ที่Wayback Machine
- ↑ Yde Venema (2008)การบรรยายเกี่ยวกับแคลคูลัส μ แบบโมดอล เก็บถาวรเมื่อวันที่ 21 มีนาคม 2012 ที่Wayback Machine
- ↑ Coxeter, HSM (1942). เรขาคณิตนอกยุคยูคลิด . สำนักพิมพ์มหาวิทยาลัยโทรอนโต . หน้า36.
- ↑ GB Halsted (1906)เรขาคณิตเชิงฉายสังเคราะห์หน้า 27
- ↑ Wilson, Kenneth G. (1971). "กลุ่มการปรับมาตรฐานและปรากฏการณ์วิกฤต I. กลุ่มการปรับมาตรฐานและภาพการปรับขนาด Kadanoff" . Physical Review B . 4 (9): 3174– 3183. Bibcode : 1971PhRvB...4.3174W . doi : 10.1103/PhysRevB.4.3174 .
- ↑ Wilson, Kenneth G. (1971). "กลุ่มการปรับมาตรฐานและปรากฏการณ์วิกฤต II. การวิเคราะห์เซลล์ปริภูมิเฟสของพฤติกรรมวิกฤต" . Physical Review B . 4 (9): 3184– 3205. Bibcode : 1971PhRvB...4.3184W . doi : 10.1103/PhysRevB.4.3184 .
- ↑ "P. Cousot & R. Cousot, การตีความเชิงนามธรรม: แบบจำลองแลตติสแบบรวมสำหรับการวิเคราะห์แบบคงที่ของโปรแกรมโดยการสร้างหรือการประมาณจุดตรึง "