Trình tạo mã xấp xỉ Chebyshev

 (stuffmatic.com)
2 điểm bởi GN⁺ 2024-10-06 | 1 bình luận | Chia sẻ qua WhatsApp
  • Chebyshev approximation calculator là công cụ tạo mã xấp xỉ hàm toán học trên web
  • Người dùng có thể chỉ định f(x), x min, x max, Terms để xác định hàm cần xấp xỉ, khoảng giá trị và số hạng
  • Thông qua tùy chọn Match x min x max và khu vực Coefficients, công cụ cung cấp quy trình để xem hoặc điều chỉnh giá trị hệ số và biên của khoảng
  • Ở khu vực Generated code, kết quả tính toán được hiển thị dưới dạng mã; trong màn hình ví dụ có thể thấy các hệ số từ c0 đến c10
  • Có liên kết tới kho GitHub để có thể trực tiếp xem mã triển khai của công cụ web

Trình tạo mã xấp xỉ Chebyshev

  • Chebyshev approximation calculator tạo mã để xấp xỉ các hàm toán học một cách hiệu quả
  • Nhập các điều kiện xấp xỉ trên giao diện web
    • f(x): hàm cần xấp xỉ
    • x min: giá trị nhỏ nhất của khoảng
    • x max: giá trị lớn nhất của khoảng
    • Terms: số hạng sẽ sử dụng
    • Match x min x max: tùy chọn liên quan đến biên của khoảng

Kiểm tra hệ số và mã được tạo

  • Màn hình được chia thành khu vực Coefficients và khu vực Generated code
  • Ví dụ các hệ số hiển thị có thể xem từ c0 đến c10
    • c0 = 0.16793649417016518
    • c1 = -0.12411164956092625
    • c2 = -0.09756341588422193
    • c3 = 0.1800765790518846
    • c4 = -0.06972963647223016
    • c5 = -0.09250127939333941
    • c6 = 0.18076946080324185
    • c7 = 0.15990613621816677
    • c8 = -0.028659588693985123
    • c9 = -0.09494966104347571
    • c10 = -0.04980429834982578
  • Trên màn hình cũng hiển thị các mục hệ số từ c11 đến c39

Kho mã

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-10-06
Ý kiến trên Hacker News

  • Hay thật. Khoảng năm 1974, tôi từng viết một hàm tính căn bậc hai bằng assembly IBM 360 và được trả tiền
    Lúc đó tôi đang học năm cuối đại học, và được yêu cầu làm sao cho hiệu quả nhất có thể. Tôi scale đầu vào về khoảng từ 0 đến 1, dùng xấp xỉ Chebyshev cho ước lượng ban đầu, rồi tìm nghiệm bằng cách áp dụng 2 hay 3 vòng lặp gì đó của phương pháp Newton đã được trải ra. Đó là khoản thu nhập đầu tiên tôi kiếm được nhờ viết code

    • Tôi thích những câu chuyện như thế này. Tôi vẫn còn nhớ cảm giác như được mở mắt khi lần đầu nhận ra tiềm năng của tính toán trong buổi học đầu tiên về giải tích số

  • Làm thật sự tốt. Tôi bị cuốn hút bởi mức độ hiệu quả của những phép xấp xỉ kiểu này, và cũng hiểu thêm rất nhiều vì sao các hàm lượng giác hay các hàm toán học khác trên máy tính 8-bit lại được triển khai như vậy
    BBC Research Department năm 1969 cũng có một tài liệu gốc rất hay nói về lý do cách này tuyệt vời: https://downloads.bbc.co.uk/rd/pubs/reports/1969-10.pdf
    Nếu bạn mới chỉ biết xấp xỉ Taylor thì ban đầu nó có thể trông hơi như ma thuật

    • Đúng vậy. Cả khía cạnh toán học cũng thế, và việc trên thực tế nó quy về chỉ vài dòng code cũng khiến nó khá giống ma thuật

  • Trước đây tôi từng đạt kết quả tốt với Sollya: https://www.sollya.org/
    Tuy kết quả tốt, nhưng bản thân phần mềm thì hơi phiền khi dùng

    • Sollya có lẽ là công cụ hiện đại tốt nhất cho kiểu công việc này. Bên trong nó thực hiện xấp xỉ Remez rồi dùng LLL để lượng tử hóa sang số dấu phẩy động, chứ không dùng trực tiếp Chebyshev

  • Khi xấp xỉ Math.sin(x)/x, tức hàm sinc, trên đoạn [-3,3] bằng 7 hạng, toàn bộ các hệ số c0...c6 đều thành NaN. Đây có phải bug không?
    Tôi tạm xử lý bằng cách ép đơn giản thành 1.0 khi x gần 0
    if(Math.abs(x) > 1e-8 ){ Math.sin(x)/x } else { 1.0 }

    • Khó gọi chính xác là bug. Có lẽ code đánh giá hàm tại các điểm lưới kiểu x_j = (xmin) + (xmax - xmin)/2(1 + cos(pi[0..j-1]/(j-1)) để tìm hệ số Chebyshev; nếu một trong số đó đúng bằng 0 thì sẽ tính Math.sin(0)/0, dẫn đến NaN
      Một cách né khác là dùng khoảng hơi bất đối xứng như [-3,+3.0000001]
    • Vấn đề ở đây là biểu thức đầu tiên không được định nghĩa tốt tại x=0, và có vẻ code xấp xỉ bị vấp ở đó. Code hơi đáng tiếc
    • Đúng, đó là bug. Nếu hàm không được định nghĩa tại mọi nút Chebyshev thì ứng dụng nên hiển thị lỗi. Như bạn đã tìm ra, hiện giờ có thể dễ dàng né được

  • Đa thức Chebyshev quá mạnh và đa dụng trong xấp xỉ, đến mức mọi người nghĩ nó hay đến mức giống lừa đảo nên lại không dùng
    Phương pháp đầu tiên nên thử phải là Chebyshev. Mạng nơ-ron nên là phương án cuối cùng

  • Tuyệt vời. Gần đây tôi muốn làm việc kiểu này, nhưng việc tìm code tính xấp xỉ lại khó một cách đáng ngạc nhiên
    Tôi đã bookmark để lần tới cần xấp xỉ nhanh một hàm thì dùng

    • Tôi cũng ngạc nhiên vì khó tìm được code xấp xỉ Chebyshev thực sự chạy được. Hy vọng dự án này sẽ thay đổi điều đó

  • Chebyshev giống như ma thuật hắc ám. Dù đã xem phần suy diễn trong một lớp cao học, tôi vẫn thấy vậy

  • Cũng nhất định phải nhắc tới Chebfun của Nick Trefethen và những người khác. Đây là công cụ mở rộng nội dung này theo hầu như mọi hướng có thể nghĩ tới
    Có thể xem Chebfuns là đối ứng dành cho hàm, giống như số dấu phẩy động đối ứng với các số toán học thực. Đó là một phần mềm thật sự ấn tượng
    https://www.chebfun.org

    • Đồng ý. Các phương pháp bên đó rất mạnh và nhanh. Dùng các kỹ thuật dựa trên Chebyshev và hàm siêu cầu có thể xấp xỉ hầu hết hàm rất nhanh tới mức chính xác máy, rồi sau đó thao tác biểu diễn đó dễ hơn
      Nhờ vậy có thể làm nhiều việc như tìm nghiệm của phương trình vi phân-đại số với độ chính xác máy, hoặc tìm cực tiểu/cực đại toàn cục của hàm một biến
      Tôi biết hiện nay họ dùng thuật toán khác, nhưng phương pháp luận cơ bản Chebfun từng dùng có thể xem trong chương 6 sách Spectral Methods in Matlab của Trefethen. Phương pháp luận mới hơn dùng hàm siêu cầu có trong bài SIAM Review A Fast and Well-Conditioned Spectral Method của Olver và Townsend

  • Tôi có một điều tò mò, không biết hỏi ở đây có được không. Trước đây tôi xem một video nói rằng Nintendo 64 không đủ khả năng tính hàm sin nên dùng bảng tra cứu từ 0 đến 2π, và còn dùng các kỹ thuật thông minh để giảm kích thước bảng
    Liệu có thể huấn luyện mạng nơ-ron rồi lưu trọng số, hoặc tạo một hàm rồi lưu các hệ số để tính sin và cos không?

    • Mạng nơ-ron thường dùng các hàm lượng giác ở bên trong, nên sẽ cần nhiều phép tính hơn rất nhiều so với cần thiết
      Nếu còn dư chút chu kỳ CPU, có thể dùng xấp xỉ lai: lấy giá trị từ một bảng tra cứu thưa làm ước lượng ban đầu rồi lặp vài lần bằng kỹ thuật xấp xỉ số. Hoặc như bài gốc, chỉ cần lưu vài hệ số đầu của xấp xỉ đa thức
    • Nếu chưa quen thì nên xem CORDIC. Trước đây đó là một mẹo lượng giác phổ biến, và hiện nay vẫn được dùng ở mức nào đó trong mảng nhúng
      Mạng nơ-ron có thể hữu ích khi bạn có các mẫu của một hàm nào đó nhưng không biết xấp xỉ nó thế nào; ở đây thì không phải trường hợp đó
    • Huấn luyện mạng nơ-ron để tính bất kỳ hàm nào dĩ nhiên là có thể, nhưng với một hàm đã quá rõ như sin thì hoàn toàn vô lý
      Mạng nơ-ron là lời giải tuyệt vời khi cần đánh giá những đối tượng khó phân tích về mặt toán học, nhưng đã có rất nhiều kỹ thuật đã biết để tính và xấp xỉ các hàm lượng giác
      Huấn luyện mạng nơ-ron để tính sin giống như phiên bản toán học của việc dùng LLM để đảo ngược chuỗi. Làm được, nhưng đó chỉ là ý tưởng bạn nghĩ tới khi không biết rằng vấn đề này về bản chất đã được giải bằng cách tiếp cận trực tiếp hơn
      Trước khi dùng kỹ thuật AI/ML, luôn đáng kiểm tra xem các nhà toán học đã có lời giải chưa. Ngày nay có khả năng rất nhiều công sức đang được đổ vào việc gắn AI/ML cho những bài toán mà chỉ là lập trình viên không biết rằng đã có lời giải nổi tiếng, hiệu quả, thậm chí tối ưu
    • Mạng nơ-ron về bản chất là khớp đường cong, nên có thể làm được. Video này có thể hữu ích: https://www.youtube.com/watch?v=FBpPjjhJGhk But what is a neural network REALLY?
      Điểm mạnh chính của mạng nơ-ron bộc lộ khi có rất nhiều đầu vào, chứ không chỉ vài đầu vào. Với trường hợp đơn giản như sin(x), có những phương pháp khác như công cụ được đăng ở đây
    • Kỹ thuật tiết kiệm thường dùng là chỉ lưu bảng từ 0 đến π/2, rồi dùng 2 bit chỉ số bổ sung để tạo ra ba góc phần tư còn lại

  • Rất tuyệt. Tôi nổi hứng nghịch thử xem có thể tạo ra một hàm khó xấp xỉ tốt nhanh đến mức nào
    Cho tới giờ thì Math.cos(x * Math.exp(Math.cos(x * x))) là tốt nhất. Vì có nhiều phép hợp thành nên nó tạo ra dao động nhanh và độ dốc lớn, khiến Chebyshev khó xấp xỉ dễ dàng