กลับไปหน้าบทความ

อ่าน 5 นาที

ไม่มีชื่อบทความ

ใน ทางคณิตศาสตร์ จุด ตรึง (บางครั้ง ย่อว่า fixpoint ) หรือที่เรียกว่า จุดไม่เปลี่ยนแปลง คือค่าที่ไม่เปลี่ยนแปลงภายใต้ การแปลง ที่กำหนด โดยเฉพาะอย่างยิ่งสำหรับ ฟังก์ชัน...

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

ฟังก์ชันเอฟ(x)=x33x2+3x{\displaystyle f(x)=x^{3}-3x^{2}+3x}(แสดงด้วยสีแดง) มีจุดคงที่คือ 0, 1 และ 2

ในทางคณิตศาสตร์จุดตรึง (บางครั้ง ย่อว่า fixpoint ) หรือที่เรียกว่าจุดไม่เปลี่ยนแปลงคือค่าที่ไม่เปลี่ยนแปลงภายใต้การแปลง ที่กำหนด โดยเฉพาะอย่างยิ่งสำหรับฟังก์ชันจุดตรึงคือองค์ประกอบที่ถูกแปลงไปยังตัวมันเองโดยฟังก์ชันนั้น เซตของจุดตรึงใดๆ ของการแปลงก็เรียกว่าเซตไม่ เปลี่ยนแปลงเช่นกัน

จุดคงที่ของฟังก์ชัน

ตามหลักการแล้วcเป็นจุดตรึงของฟังก์ชันf ก็ ต่อ เมื่อcอยู่ในทั้งโดเมนและโคโดเมนของfและf ( c ) = cโดยเฉพาะอย่างยิ่งfจะไม่มีจุดตรึงใดๆ เลยหากโดเมนของ f แยกออกจากโคโดเมน ถ้าfถูกนิยามบนจำนวนจริงในทางกราฟิกแล้ว f จะสอดคล้องกับเส้นโค้งในระนาบยุคลิดและจุดตรึงc แต่ละจุด จะสอดคล้องกับจุดตัดของเส้นโค้งกับเส้นตรงy = xดังแสดงในภาพ

ตัวอย่างเช่น ถ้าfถูกกำหนดบนจำนวนจริงโดย เอฟ(x)=x23x+4,{\displaystyle f(x)=x^{2}-3x+4,} ดังนั้น 2 จึงเป็นจุดคงที่ของfเพราะ f (2) = 2

ไม่ใช่ทุกฟังก์ชันจะมีจุดตรึง: ตัวอย่างเช่นf ( x ) = x + 1ไม่มีจุดตรึง เพราะx + 1จะไม่เท่ากับxสำหรับจำนวนจริงใดๆ

การวนซ้ำจุดคงที่

ในการวิเคราะห์เชิงตัวเลขการวนซ้ำจุดตรึงเป็นวิธีการคำนวณจุดตรึงของฟังก์ชัน โดยเฉพาะอย่างยิ่ง เมื่อกำหนดฟังก์ชันมาให้เอฟ{\displaystyle f}ด้วยโดเมนและโคโดเมนเดียวกัน จุดหนึ่งx0{\displaystyle x_{0}}ในขอบเขตของเอฟ{\displaystyle f}การวนซ้ำจุดคงที่คือ

xn+1=เอฟ(xn),n=0,1,2,{\displaystyle x_{n+1}=f(x_{n}),\,n=0,1,2,\dots }

ซึ่งก่อให้เกิดลำดับx0,x1,x2,{\displaystyle x_{0},x_{1},x_{2},\dots }ของการประยุกต์ใช้ฟังก์ชันแบบวนซ้ำx0,เอฟ(x0),เอฟ(เอฟ(x0)),{\displaystyle x_{0},f(x_{0}),f(f(x_{0})),\dots }ซึ่งหวังว่าจะมาบรรจบกันที่จุดหนึ่งx{\displaystyle x}. ถ้าเอฟ{\displaystyle f}ถ้าค่าที่ได้มีความต่อเนื่อง ก็สามารถพิสูจน์ได้ว่าค่าที่ได้นั้นมีความต่อเนื่องเช่นกันx{\displaystyle x}เป็นจุดคงที่ของเอฟ{\displaystyle f}.

แนวคิดเรื่องจุดคงที่ดึงดูด จุดคงที่ผลักดัน และจุดคาบถูกกำหนดขึ้นโดยสัมพันธ์กับการวนซ้ำของจุดคงที่

ทฤษฎีบทจุดตรึง

ทฤษฎีบทจุดตรึงเป็นผลลัพธ์ที่กล่าวว่ามีจุดตรึงอย่างน้อยหนึ่งจุดภายใต้เงื่อนไขทั่วไปบางประการ[ 1 ]

ตัวอย่างเช่นทฤษฎีบทจุดตรึงของ Banach (1922) ให้เกณฑ์ทั่วไปที่รับประกันว่า หากเป็นไปตามเกณฑ์นี้การวนซ้ำจุดตรึงจะลู่เข้าสู่จุดตรึงเสมอ

ทฤษฎีบทจุดตรึงของบราวเวอร์ (1911) กล่าวว่าฟังก์ชันต่อเนื่อง ใดๆ จากทรงกลมหน่วย ปิด ในปริภูมิยุคลิดมิติnไปยังตัวมันเองจะต้องมีจุดตรึง แต่ไม่ได้อธิบายวิธีการหาจุดตรึงนั้น

ทฤษฎีบทจุดตรึงของเลฟเชตซ์ ( และทฤษฎีบทจุดตรึงของนีลเซน ) จากโทโพโลยีเชิงพีชคณิตให้วิธีการนับจำนวนจุดตรึง

จุดคงที่ของการกระทำของกลุ่ม

ในพีชคณิตสำหรับกลุ่มGที่กระทำต่อเซตXด้วยการกระทำของกลุ่ม{\displaystyle \cdot }กล่าวได้ ว่าxในXเป็นจุดคงที่ของgถ้าจีx=x{\displaystyle g\cdot x=x}.

กลุ่มย่อยจุดคงที่จีเอฟ{\displaystyle G^{f}}ของออโตมอร์ฟิซึมfของกลุ่มGคือกลุ่มย่อยของG : จีเอฟ={จีจีเอฟ(จี)=จี}.{\displaystyle G^{f}=\{g\in G\mid f(g)=g\}.}

ในทำนองเดียวกันวงแหวนย่อยจุดคงที่อาร์เอฟ{\displaystyle R^{f}}ของออโตมอร์ฟิซึมfของริงRคือซับริงของจุดตรึงของfนั่นคือ อาร์เอฟ={อาร์เอฟ()=}.{\displaystyle R^{f}=\{r\in R\mid f(r)=r\}.}

ในทฤษฎีกาโลอิสเซตของจุดตรึงของเซตออโตมอร์ฟิซึมของฟิลด์ หนึ่ง เรียกว่าฟิลด์ตรึงของเซตออโตมอร์ฟิซึม

คุณสมบัติจุดตรึงเชิงทอพอโลยี

ปริภูมิเชิงทอพอโลยีX{\displaystyle X}กล่าวได้ว่ามีคุณสมบัติจุดตรึง (FPP) ถ้าสำหรับฟังก์ชันต่อเนื่อง ใดๆ

เอฟ:XX{\displaystyle f\colon X\to X}

มีอยู่จริงxX{\displaystyle x\in X}โดยที่เอฟ(x)=x{\displaystyle f(x)=x}.

FPP เป็นค่าคงที่เชิงทอพอโลยีกล่าวคือ มันถูกรักษาไว้โดยโฮมีโอเมอร์ฟิซึม ใดๆ นอกจากนี้ FPP ยังถูกรักษาไว้โดยการหดกลับ ใดๆ ด้วย

ตามทฤษฎีบทจุดตรึงของ Brouwer เซตย่อยที่กระชับและนูน ทุกเซตในปริภูมิยุคลิดจะมี FPP ความกระชับเพียงอย่างเดียวไม่ได้หมายความถึง FPP และความนูนก็ไม่ใช่คุณสมบัติทางโทโพโลยีด้วยซ้ำ ดังนั้นจึงสมเหตุสมผลที่จะถามว่าจะกำหนดลักษณะทางโทโพโลยีของ FPP ได้อย่างไร ในปี 1932 Borsukถามว่าความกระชับร่วมกับความสามารถในการหดตัวสามารถเป็นเงื่อนไขที่จำเป็นและเพียงพอสำหรับ FPP ได้หรือไม่ ปัญหานี้ยังคงเปิดอยู่เป็นเวลา 20 ปี จนกระทั่ง Kinoshita พิสูจน์ได้ว่าข้อสันนิษฐานนี้ไม่ถูกต้อง โดยเขาพบตัวอย่างของปริภูมิที่กระชับและหดตัวได้โดยไม่มี FPP [ 2 ]

จุดคงที่ของลำดับบางส่วน

ในทฤษฎีโดเมนแนวคิดและศัพท์เฉพาะของจุดตรึงจะถูกขยายไปสู่ลำดับบางส่วนให้ ≤ เป็นลำดับบางส่วนเหนือเซตXและให้f : XXเป็นฟังก์ชันเหนือXแล้วจุดตรึงก่อนหน้า (หรือสะกดว่าpre-fixed pointบางครั้งย่อเป็นprefixpointหรือpre-fixpoint ) ของfคือp ใดๆ ที่f ( p ) ≤ p ใน ทำนองเดียวกันจุดตรึงหลัง ของfคือp ใดๆ ที่pf ( p ) [ 3 ] บางครั้งมีการใช้ในทางตรงกันข้าม[ 4 ] Malkis ให้เหตุผลนิยามที่นำเสนอไว้ที่นี่ดังนี้: "เนื่องจากfอยู่ก่อนเครื่องหมายอสมการในเทอมf ( x ) ≤ xดังนั้นx ดังกล่าว จึงเรียกว่า จุดตรึง ก่อน หน้า " [ 5 ]จุดตรึงคือจุดที่เป็นทั้งจุดตรึงก่อนหน้าและจุดตรึงหลัง จุดตรึงก่อนหน้าและจุดตรึงหลังมีการประยุกต์ใช้ในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี[ 6 ]

จุดคงที่น้อยที่สุด

ในทฤษฎีลำดับจุดตรึงที่เล็กที่สุดของฟังก์ชันจากเซตที่มีลำดับบางส่วน (poset) ไปยังตัวมันเอง คือจุดตรึงที่เล็กกว่าจุดตรึงอื่นๆ ทุกจุด ตามลำดับของ poset นั้น ฟังก์ชันไม่จำเป็นต้องมีจุดตรึงที่เล็กที่สุด แต่ถ้ามี จุดตรึงที่เล็กที่สุดนั้นจะต้องมีเพียงหนึ่งเดียว

วิธีหนึ่งในการแสดงทฤษฎีบท Knaster–Tarskiคือการกล่าวว่าฟังก์ชันโมโนโทนบนแลตทิซที่สมบูรณ์มีจุดตรึงน้อยที่สุดที่ตรงกับจุดพรีฟิกพอยต์น้อยที่สุด (และในทำนองเดียวกัน จุดตรึงมากที่สุดจะตรงกับจุดโพสต์ฟิกพอยต์มากที่สุด) [ 7 ]

ตัวรวมจุดคงที่

ในตรรกศาสตร์เชิงผสมสำหรับวิทยาการคอมพิวเตอร์ ตัวรวมจุดคงที่ (fixed-point combinator) คือฟังก์ชันลำดับสูงกว่าเอฟฉันx{\displaystyle {\mathsf {fix}}}ฟังก์ชันนี้จะส่งคืนค่าจุดคงที่ของฟังก์ชันอาร์กิวเมนต์ หากมีอยู่ กล่าวคือ ถ้าฟังก์ชันfมีจุดคงที่ตั้งแต่หนึ่งจุดขึ้นไป แล้ว

เอฟฉันxเอฟ=เอฟ(เอฟฉันxเอฟ).{\displaystyle \operatorname {\mathsf {fix}} f=f(\operatorname {\mathsf {fix}} f).}

ตรรกะจุดคงที่

ในตรรกศาสตร์เชิงคณิตศาสตร์ตรรกศาสตร์จุดตรึง (fixed-point logics) เป็นส่วนขยายของตรรกศาสตร์ภาคแสดงแบบคลาสสิก (classical predicate logic) ที่ถูกนำมาใช้เพื่อแสดงการเรียกซ้ำ (recursion) การพัฒนาตรรกศาสตร์ประเภทนี้ได้รับแรงบันดาลใจจากทฤษฎีความซับซ้อนเชิงพรรณนา (descriptive complexity theory)และความสัมพันธ์กับภาษาการสอบถามฐานข้อมูลโดยเฉพาะอย่างยิ่งกับDatalog

แอปพลิเคชัน

ในหลายสาขา สภาวะสมดุลหรือเสถียรภาพเป็นแนวคิดพื้นฐานที่สามารถอธิบายได้ในแง่ของจุดคงที่ ตัวอย่างบางส่วนมีดังต่อไปนี้

ดูเพิ่มเติม

หมายเหตุ

  1. Brown, RF, บรรณาธิการ (1988). ทฤษฎีจุดตรึงและการประยุกต์ใช้ . สมาคมคณิตศาสตร์อเมริกัน. ISBN 0-8218-5080-6.
  2. 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 . 
  3. 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 . 
  4. Patrick Cousot; Radhia Cousot (1979). "เวอร์ชันเชิงสร้างสรรค์ของทฤษฎีบทจุดตรึงของ Tarski" (PDF) . Pacific Journal of Mathematics . 82 (1): 43– 57. doi : 10.2140/pjm.1979.82.43 .
  5. 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 
  6. Yde Venema (2008)การบรรยายเกี่ยวกับแคลคูลัส μ แบบโมดอล เก็บถาวรเมื่อวันที่ 21 มีนาคม 2012 ที่Wayback Machine
  7. Yde Venema (2008)การบรรยายเกี่ยวกับแคลคูลัส μ แบบโมดอล เก็บถาวรเมื่อวันที่ 21 มีนาคม 2012 ที่Wayback Machine
  8. Coxeter, HSM (1942). เรขาคณิตนอกยุคยูคลิด . สำนักพิมพ์มหาวิทยาลัยโทรอนโต . หน้า36. 
  9. GB Halsted (1906)เรขาคณิตเชิงฉายสังเคราะห์หน้า 27
  10. Wilson, Kenneth G. (1971). "กลุ่มการปรับมาตรฐานและปรากฏการณ์วิกฤต I. กลุ่มการปรับมาตรฐานและภาพการปรับขนาด Kadanoff" . Physical Review B . 4 (9): 3174– 3183. Bibcode : 1971PhRvB...4.3174W . doi : 10.1103/PhysRevB.4.3174 .
  11. Wilson, Kenneth G. (1971). "กลุ่มการปรับมาตรฐานและปรากฏการณ์วิกฤต II. การวิเคราะห์เซลล์ปริภูมิเฟสของพฤติกรรมวิกฤต" . Physical Review B . 4 (9): 3184– 3205. Bibcode : 1971PhRvB...4.3184W . doi : 10.1103/PhysRevB.4.3184 .
  12. "P. Cousot & R. Cousot, การตีความเชิงนามธรรม: แบบจำลองแลตติสแบบรวมสำหรับการวิเคราะห์แบบคงที่ของโปรแกรมโดยการสร้างหรือการประมาณจุดตรึง "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ไม่มีชื่อบทความ

ใน ทางคณิตศาสตร์ จุด ตรึง (บางครั้ง ย่อว่า fixpoint ) หรือที่เรียกว่า จุดไม่เปลี่ยนแปลง คือค่าที่ไม่เปลี่ยนแปลงภายใต้ การแปลง ที่กำหนด โดยเฉพาะอย่างยิ่งสำหรับ ฟังก์ชัน...

จุดคงที่ของฟังก์ชัน

ตามหลักการแล้ว c เป็นจุดตรึงของฟังก์ชัน f ก็ ต่อ เมื่อ c อยู่ในทั้ง โดเมน และ โคโดเมน ของ f และ f ( c ) = c โดยเฉพาะอย่างยิ่ง f จะไม่มีจุดตรึงใดๆ เลยหากโดเมนของ f แยกออกจากโคโดเมน ถ้า f ถูกนิยามบน จำนวนจริง ในทางกราฟิกแล้ว f จะสอดคล้องกับ เส้นโค้ง ใน...

การวนซ้ำจุดคงที่

ใน การวิเคราะห์เชิง ตัวเลข การวนซ้ำจุดตรึง เป็นวิธีการคำนวณจุดตรึงของฟังก์ชัน โดยเฉพาะอย่างยิ่ง เมื่อกำหนดฟังก์ชันมาให้ เอฟ {\displaystyle f} ด้วยโดเมนและโคโดเมนเดียวกัน จุดหนึ่ง x 0 {\displaystyle x_{0}} ในขอบเขตของ เอฟ {\displaystyle f} การวนซ้ำจุดคงที่คือ

ทฤษฎีบทจุดตรึง

ทฤษฎีบทจุดตรึงเป็นผลลัพธ์ที่กล่าวว่ามีจุดตรึงอย่างน้อยหนึ่งจุดภายใต้เงื่อนไขทั่วไปบางประการ [ 1 ]